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

Heather ·

更新时间:2024-11-15

· 994 次阅读

你有 102010^{20}1020 个格子，它们从 00 开始编号，初始时所有格子都还未染色，现在你按如下规则对它们染色：

编号是 p1p_1p1 倍数的格子（包括 00 号格子，下同）染成红色。编号是 p2p_2p2 倍数的格子染成蓝色。编号既是 p1p_1p1 倍数又是 p2p_2p2 倍数的格子，你可以选择染成红色或者蓝色。

其中 p1p_1p1 和 p2p_2p2 是给定的整数，若格子编号是 p1p_1p1 或 p2p_2p2 的倍数则它必须要被染色。在忽略掉所有未染色格子后，你不希望存在 kkk 个连续的格子颜色相同，因为你认为这种染色方案是无聊的。现在给定 p1p_1p1 , p2p_2p2 , kkk ，你想知道是否有一种染色方案不是无聊的。

注意特判 k=1k=1k=1

#include 
using namespace std;
typedef long long ll;
templateinline void read(T &FF){
	T RR=1;FF=0;char CH=getchar();
	for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
	for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
	FF*=RR;
}
ll gcd(ll x,ll y){
	if(x%y==0)return y;
	return gcd(y,x%y);
}
int main(){
//	freopen("color.in","r",stdin);
//	freopen("color.out","w",stdout);
	int T;
	read(T);
	while(T--){
		ll x,y,z;
		read(x);read(y);read(z);
		if(z==1)cout<<"NO"<<endl;
		else{
			ll m=gcd(x,y);
			x/=m;
			y/=m;
			z--;
			if(x*z+1<y||y*z+1<x)puts("No");
			else puts("Yes");
		}
	}
	return 0;
}

作者：zhk1211

1024 个赞