CF1260C Infinite Fence

数学结论题，现场却卡得我基本掉色

难度在于对数学式的敏感度

题解：

假设r<=b（如果不是就交换）

首先思考r，b互质的情况，发现一定会存在第pos个木板涂蓝色，而第pos+1个木板涂成红色的情况

也就是说$rx-by=1$一定有正整数解存在，这一点可以用裴蜀定理简单的证明

（在P1082 同余方程的题解里，你也许可以得到更好的证明）

这意味着如果要OBEY，那么区间[pos,pos+b]中的红色木板数量一定要小于k，也就是

（该式的意思是pos以后的k-1块红木板要能够卡满，甚至超过这个长度为b的区间）

此时又可以发现对于r，b不互质的情况，如果我们只看那些能被gcd(r,b)整除的木板，它们的情况又是与上述情况相同的

换句话说，只要先将r，b都除去gcd(r,b)使两者互质，再套用上述判定式即可

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

#define int long long

int t,r,b,k;

void doit(){
    read(r);read(b);read(k);
    int gcd=__gcd(r,b);
    r/=gcd;
    b/=gcd;
    if(r>b) swap(r,b);
    if((k-1)*r+1>=b) puts("OBEY");
    else puts("REBEL");
}

signed main(){
    read(t);
    while(t--) doit();
}
赏

fighter