题目
题目链接：https://www.luogu.com.cn/problem/P6476
你有 \(10^{20}\) 个格子，它们从 \(0\) 开始编号，初始时所有格子都还未染色，现在你按如下规则对它们染色：
- 编号是 \(p_1\) 倍数的格子（包括 \(0\) 号格子，下同）染成红色。
- 编号是 \(p_2\) 倍数的格子染成蓝色。
- 编号既是 \(p_1\) 倍数又是 \(p_2\) 倍数的格子，你可以选择染成红色或者蓝色。
其中 \(p_1\) 和 \(p_2\) 是给定的整数，若格子编号是 \(p_1\) 或 \(p_2\) 的倍数则它必须要被染色。在忽略掉所有未染色格子后，你不希望存在 \(k\) 个连续的格子颜色相同，因为你认为这种染色方案是无聊的。现在给定 \(p_1\), \(p_2\), \(k\)，你想知道是否有一种染色方案不是无聊的。
思路：
结论题。考场没有特判 \(k=1\)，
首先 \(k=1\) 时，输出 No。
容易发现只有相对小的数可能会被连续染上 \(k\) 个，所以如果一个数同时为 \(p_1,p_2\) 的倍数，那么肯定选择 \(p_2\) 更优。我们设 \(a\) 是较小数，\(b\) 是较大数。
我们设两个连续的 \(b\) 的倍数分别为 \(p,q(p<q)\)。为了我们就是要找是否存在一对 \(p,q\)，使得 \((p,q)\) 中有 \(k\) 个 \(a\) 的倍数。
那么我们其实只要找到距离上一个 \(b\) 的倍数最小的 \(a\) 的倍数，判断能否选择连续 \(k\) 个 \(a\) 的倍数即可。说人话，就是对于所有的 \(ax\)，取 \(ax\bmod b\) 最小的 \(x\) 来判断能否放连续 \(k\) 个 \(a\) 即可。
根据裴蜀定理，\(ax\bmod b\) 除了 0 以外，最小只能为 \(\gcd(a,b)\)。而我们如果能确定在 \(10^{20}\) 内，对于每一组 \(a,b\) 必然存在一个 \(ax\leq 10^{20}\) 满足 \(ax\bmod b=\gcd(a,b)\)，那么这道题就好办了。
因为 \(ax\bmod b\) 是有长度不超过 \(b\) 的循环节的，而 \(a,b\) 均 \(\leq 10^9\)，所以在不超过 \(10^{18}\) 时就一定会出现 \(ax\bmod b=\gcd(a,b)\) 的情况。
那么我们只需要判断 \(\gcd(a,b)+a(k-1)\) 是否严格小于 \(b\) 即可。
代码
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int a,b,k,d,T;
inline int read()
{
int d=0; char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) d=(d<<3)+(d<<1)+ch-48,ch=getchar();
return d;
}
int Gcd(int x,int y)
{
if (!y) return x;
return Gcd(y,x%y);
}
int main()
{
// freopen("color.in","r",stdin);
// freopen("color.out","w",stdout);
T=read();
while (T--)
{
a=read(); b=read(); k=read()-1;
if (!k) // 比赛没特判啊啊啊啊/kk
{
puts("No");
continue;
}
if (a>b) swap(a,b);
d=Gcd(b,a);
if (1LL*a*k+d<b) puts("No");
else puts("Yes");
}
return 0;
}