CF-1260C Infinite Fence 题解

题目大意

从0开始有$10^{100}$堵墙，当序号为b的倍数时，涂成蓝色，当序号为r的倍数时，涂成红色，当既是b的倍数又是r的倍数时，可以任意选择颜色。问连续相同颜色的墙的数量是否大于k。

解题思路

这个题是真的坑。。

我想了好久，但是我的思路一直wa。。

没想到什么好的方法，最后还是去看了题解。。

发现我的思路很接近正解了，就是找的区间不一样。

正解的区间是两个区间起点最近的一个区间，我是$[b,2b]$。。

其实这种题还是挺考验数学思维的。

首先，我们假设r小于b。

显然，最长的连续的区间肯定是在两个b的倍数之间的。

那么对于r来说，最长的区间长度就是b-1。

接下来就需要找到r的区间了。

设b的区间为$[n_1b,n_2b]$。

设距离左端点最近的距离为l。

那么则有$n_1b+t=kr$，由拓欧得，式子可以变为$n_1b+kr=t$，当$gcd(b,r)|t$时有解，t最小为$gcd(b,r)$。

得到r的区间长度为$(b-1)-gcd(b,r)$。

所以这个区间的红色木板的个数为$\frac{(b-1)-gcd(b,r)}{r}+1$,显然，这个也是最大的连续的个数。

判断这个与k的大小关系即可。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {
	return !b ? a: gcd(b, a % b);
}

int main() {
	int t,m;
	cin >> t;
	while (t--) {
		ll r, b, k;
		cin >> r >> b >> k;
		if (r > b)	swap(r, b);
		ll ans = (b - 1 - gcd(r, b)) / r + 1;
		if (ans>=k)	cout << "REBEL" << endl;
		else cout << "OBEY" << endl;
	}
}