Educational Codeforces Round 77 (Rated for Div. 2) C. Infinite Fence

发表于 分类于

链接

https://codeforces.com/contest/1260/problem/C

题意

下标从 $0$ 开始，已知 $r,c,k$

若下标能被 $r$ 整除，则标记为红色

若下标能被 $b$ 整除，则标记为蓝色

若下标能同时被 $r$ 和 $b$ 整除，则可以标记为两种颜色之一

在所有被标记的下标里不能有 $k$ 个连续的颜色相同的下标

思路

裴蜀定理：$a \times x+b \times y=c$ ，仅当 $gcd(a,b)\mid{c}$ 时等式成立

设 $b>r$

当 $y\times b$ 被染为蓝色，最近的 $x\times r$ 离 $y\times b$ 的距离 $c_{min}=gcd(b,r)$

根据题意：$x \times r+(k-1) \times r\ge y \times b+b\longrightarrow y \times b+gcd(b,r)+(k-1) \times r\ge y \times b+b$

所以 $gcd(b,r)+(k-1) \times r-b\ge 0$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) {
    return b?gcd(b,a%b):a;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--) {
    	ll r,b,k;
    	cin>>r>>b>>k;
    	if(r>b) swap(r,b);
    	if(gcd(b,r)+(k-1)*r>=b) cout<<"OBEY"<<endl;
    	else cout<<"REBEL"<<endl;
    }
    return 0;
}