CF-1340B

67/100

题意：

你现在有一条无限长的栅栏，假设开头为0，现有两种颜料$a，b$，设当前下标为$i$，当$i\%a=0$时涂$a$，当$i\%b=0$时涂$b$，当两者都满足是任涂一种，其余情况不涂，限制要求：以涂的栅栏，连续的颜色不能超过$k$个，问是否能满足所有要求。

题解：

设较大的为$a$，不难发现，当$gcd(a,b)=1$时，一定存在一个下标$pos$满足$pos\%a=0$且$(pos+1)\%b=0$，证明：由裴蜀定理得，一定存在一组正整数解$x，y$满足$ax-by=1$，则从当前的$pos$到$pos+a$，是$b$出现最多的区间，即$\frac {(a-2)}{b}+1$个$b$，则当$\frac {(a-2)}{b}+1<k$时符合要求。当$gcd(a,b)\ne1$时，只需要同除以$gcd$即可，答案不受影响。

AC：

int T;cin>>T;
  while(T--){
    ll r,b,k;cin>>r>>b>>k;
    if(r<b)swap(r,b);
    int g=gcd(r,b);
    r/=g,b/=g;
    if(r-1<=(k-1)*b)cout<<"OBEY\n";
    else cout<<"REBEL\n";
   }

• 本文作者： baddog
• 本文链接： https://katoli.github.io/2021/06/16/CF-1340B/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！