CF1260C Infinite Fence 题解

· · 题解

题意

看翻译。

重题：P6476 [NOI Online #2 提高组] 涂色游戏
话说 CCF 经典重题。

分析

只需要一个循环节即可。

其实就是看 (x+1)b-1-(x b+1)=b-2 个格子中全部是 r 倍数（红色）的情况行不行，当然前提是两者互质且 b>r。

只需要考虑这一个循环是因为这题具有周期性（两者的最小公倍数）。
题目中的 10^{100} 纯纯唬人。

代码

int main()
{
   int T=read();
    while(T--)
    {
        int r=read(),b=read(),k=read();
        if(k==1) puts("REBEL");
        else if(r==b) puts("OBEY");//特判，相当于随便放。
        else{
            int g=__gcd(r,b);r=r/g,b/=g;//使两者互质
            if(b<r) swap(r,b);
            if((b-2)/r+1>=k) puts("REBEL");
            else puts("OBEY");
        }

    }
    return 0;
}

解释一下算出来的个数为什么加一。

因为两者互质，所以不是整除，严格来说是 \left \lceil \frac{b-2}{r} \right \rceil 。