题解 P6476 【[NOI Online #2 提高组]涂色游戏】

· · 题解

这里是民间数据的 std：

不妨设 p_1<p_2，且 p_1,p_2 互质。

则会发现：最坏情况，也就是从 kp_2+1 到 (k+1)p_2-1 这个连续串内塞 p_1 所对应的颜色。

这样就有 \dfrac{p_2-2}{p_1}+1 个连续块，将其与 k 比较即可。

因为可能不互质，所以可以两边除 \gcd(p_1,p_2) 即可。 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <queue>
#include <vector>

using namespace std;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

inline int gcd(int a,int b)
{
    return !b?a:gcd(b,a%b);
}

int main()
{
    //freopen("color.in","r",stdin);
    //freopen("color.out","w",stdout);
    int T=read();
    while (T--)
    {
        int p1=read(),p2=read(),k=read();
        if (k==1)
        {
            puts("NO");
            continue;
        }
        if (p1>p2)
            swap(p1,p2);
        int GCD=gcd(p1,p2);
        p1/=GCD;
        p2/=GCD;
        puts((p2>2 && (p2-2)/p1+1>=k)?"NO":"YES");
    } 
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}