时间限制： 1.0秒空间限制： 256 MB
问题是说明你有鳟鱼，它们从开始就编号了，初期所有的鳟鱼都还没染。 现在你按以下规则把它们染色。 1 .编号为倍数的单元(包括编号单元，下同)。 2 .倍数的方格被染成蓝色的号码。 3 .号码是倍数为倍数的方格，可以选择染成红色或蓝色。 其中，和是给定的整数，格号为或的倍数时必须被染色。 忽略所有未染格后，你不希望连续的格颜相同。 因为我觉得这个染案很健谈。 现在你想知道有没有染案。
输入格式的主题包含多个数据。 第一个整数表示数据集的数量。 每组三个正整数，变量语义问题的说明。
输出形式为每组数据输出字符串，有非聊天的染案时输出“YES”，否则输出“NO”。
样品1输 4 2 10 4 2 3 6 1 4 7 1 1 2
样品1输出否是是是
示例2输837035935041691350537615920611532460366262185277924417743568232501586472891054824169842323236629660324632463246.
样品2输出是是否否否是是
数据范围和提示
测试点编号p1、p2kt13151533754610310310310481091051031125105
测试点编号p1、p2kt131410515109101620106
对于所有测试点，1t106，1P1，p2，k 10 9。
颜色问题
暴力遍历一定会超时，数据量在10^20次方水平。 Unsigned long long也是10^19级别，超出了整数的显示范围。 但是，暴力可以作为对拍，验证算法。 第一步暴力，0分。 用步骤数少的暴力，最多可以得到0~10分。 可以尽早停止检索的答案是Yes的暴力算法，最多可以得到10~20分。 寻找规律。 用a、b表示p1、p2，并且用ab表示。 大小关系不影响结果。 在B倍数的位置，都放蓝色，在公共倍数的地方也放蓝色。 这样的主题是寻找是否存在连续的k红格子块，并且是否在某两个连续的b的倍数之间。 B的倍数处是蓝色的，所以连续的块不能跨越B的倍数处。 3、对于任意给定的p、q、p q，d=gcd(p，q )，其倍数关系)即颜色关系)与p/d、q/d完全一致。 以p=4、q=10为例，如下表所示。 表1表示4、10的倍数关系，也就是颜色关系。
表1 :
0
4
8
10
12
16
20
青青
红色
红色
青青
红色
红色
0001pt;text-align:justify;">蓝表二代表2,5的倍数关系，即颜色关系：
表二：
0
2
4
5
6
8
10
蓝
红
红
蓝
红
红
蓝
这样，我们可以把给定的a，b都月份最大公约数d，这样a，b变为互质数关系。
4、通过观察或数学常识可以得到，数据倍数关系（或颜色关系）按照以lcm(a,b)为周期的规律重复。到这一步，暴力搜索可以得到大约60分。数据规模大大减小。
对于互质的a，b，现在变成求两个连续的b的倍数之间（共b-1个数字），最多有多少个a的倍数，即有多少红色格子。很显然，从b的某个倍数后面的第一个数字开始即为红色，可以有最多的红色格子。下面证明存在一个m，n，可以使：am=bn+1，即bn+1为a的整数倍。移项的：am-bn=1。因为a，b互质，根据裴蜀定理，存在整数m，n使等式成立。裴蜀定理：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。
它的一个重要推论是：a,b互质的充要条件是存在整数x,y使ax+by=1.
求最多的红色格子，由4可知，必然可以在某个区间内的b-1个格子，从第一个开始染成红色，则可以染 r=(b-1)/a。如果(b-1)%a>0，则后面还可以再染一个红色格子，r=r+1个。判断：如果r<k，有解，否则无解。或者判断 p=a(k-1)+1是否大于等于b，如果大于，则无解，否则有解。P为从第一个开始染色，染k-1个后，最后在染一个，如果p>=b，说明没有第k个红色格子的位置。Code：
#include<bits/stdc++.h>
using namespace std;
int main()
{
// freopen("color.in","r",stdin);
// freopen("color.out","w",stdout);
int t;
long long p1,p2,d,r,k,a,b;
cin>>t;
while(t--)
{
cin>>p1>>p2>>k;
if(p1>p2) { r=p1; p1=p2; p2=r; }
//algorithm中的最大公约数
d=__gcd(p1,p2); a=p1/d; b=p2/d; r=(b-1)/a;
//查看后面是否可以再放一个红色格子
if((b-1)%a>0) r++;
if(r<k) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}