codeforces-Ed77-C

codeforces-Ed77-C

七月 08, 2020

C. Infinite Fence

题意

找到nb到(n+1)b之间最多有几个r的倍数
判断最多会不会超过k个r

倍数分部性质

利用gcd首先寻找b和r的倍数间最小间隔然后尽可能填充r时判断是否会超过k个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# include <bits/stdc++.h>

 using namespace std;
 typedef long long ll;
 int main(){
    int t;cin>>t;
    while(t--){
        ll r,b,k;cin>>r>>b>>k;
        if(r>b)swap(r,b);
        ll gcd=__gcd(r,b);///每间隔n*gcd会出现一个r或b那么r和b之间最小间距等于gcd
        ///b之后第一个r和之后(k-1)个r需要的区间为r*(k-1)+gcd要严格大于等于b时才不会出现连续k个r
        if(r*(k-1)+gcd<b)cout<<"REBEL"<<endl;
        else cout<<"OBEY"<<endl;
    }
 }