codeforces 1260C. Infinite Fence (数学or裴蜀定理)

只需要验证小间隔在大间隔之间有没有连续的k个

设小间隔为a，大间隔为b，那么a在b之间出现的次数在\(\lfloor \frac{b}{a}\rfloor\)或者\(\lfloor \frac{b}{a}\rfloor+ 1\),问题转化为我们需要求a在b之间最多出现多少次和k比较即可

我的思路：

设lcm为lcm(a,b),\(c=\frac{lcm}{a}\),\(d=\frac{lcm}{b}\),那么a在b之间最多出现\(\lceil\frac{c-1}{d} \rceil\),理解为将(c-1)平均分成d段(最后一个a算作b的,所以是c-1个)

标程思路(裴蜀定理):

若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。

还是求a在b之间最多出现多少次,进一步再想,什么时候会出现最多的情况,那一定是a的起点在距离0最近的非0点上,列出式子\(ax-by=m\),m最小的时候为gcd(a,b),因此只需要验证\(gcd(a,b)+(k-1)*a\)和b的大小关系即可



#include<bits/stdc++.h>

#define ll long long

#define mk make_pair

#define ft first

#define se second

#define pii pair<int,int>

#define db double

#define ls o<<1

#define rs o<<1|1

#define lowbit(x) (x&-x)

using namespace std;

ll T, a, b, k;

ll gcd(ll a,ll b){

    if(a<b)swap(a,b);

    if(b==0)return a;

    else return gcd(b,a%b);

}

int main(){

    cin >> T;

    while(T--){

        cin >> a >> b >> k;

        if(a > b)

            swap(a, b);

        ll tp;

        if(b % a == 0){

            tp = b / a - 1;

        }else{

            ll lcm = a / gcd(a, b) * b;

            ll x = lcm / a, y = lcm / b;

            x--;

            tp = (x + y - 1) / y;

        }

        if(tp >= k)

            cout << "REBEL" << endl;

        else

            cout << "OBEY" << endl;

    }

    return 0;

}

//标程

#include<bits/stdc++.h>

using namespace std;

typedef long long li;

li a, b, k;

inline bool read() {

	if(!(cin >> a >> b >> k))

		return false;

	return true;

}

inline void solve() {

	li g = __gcd(a, b);

	a /= g;

	b /= g;

	if(a > b)

		swap(a, b);

	if((k - 1) * a + 1 < b)

		cout << "REBEL";

	else

		cout << "OBEY";

	cout << endl;

}

int main() {

#ifdef _DEBUG

	freopen("input.txt", "r", stdin);

#endif

	int tc; cin >> tc;

	while(tc--) {

		read();

		solve();

	}

	return 0;

}

巴特西

codeforces 1260C. Infinite Fence (数学or裴蜀定理)

最新文章

热门文章