自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 22:21:08，当前版本为作者最后更新于2020-04-25 13:36:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这里是民间数据的 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;
}