题意:

给你两个数a和b(1 <= a, b <= 1e4)，i-a>=0 且i-a为白，则i为白，i-b>=0且i-b为白，则i为白，

否则为黑。

其中初始化0为白。

问你是否有无穷个黑。

题解：

对这个问题，我们只需要简化：

如果并没有无限个黑，必然是存在某个数后，之后的所有数都是白色

那么必然有一个长度为b - a + 1的区间，区间中的所有数都是白色，那么之后的所有数都是白色

同时，对于任意一个白色的数c，其必然满足：ax + by = c ，gcd(a,b) | c

所以这就要求这个b - a + 1长度的区间内的数必须全部可以被gcd(a, b)整除

 

1.对于gcd(a, b) > 1

(1)对于区间长度为1，那么gcd(a, b) = a = b

那么只有a和b的倍数会为白色，因此黑色无限

(2)对于区间长度大于1，那么我们知道任意两个相邻的数都是互质的，所以它们不可能可以同时被一个大于1的数整除

那么此时就不可能出现这样一个区间。

 

2. gcd(a, b) == 1，那么必然有一个区间会满足所有的数都可以被1整除。

那么由裴蜀定理可以知道：

ax + by = gcd(a, b)必有解，x = x0, y = y0。

当gcd(a, b) = 1, 如果ax + by = c，那么解为x = cx0, y = cy0

引入麦乐鸡定理：

自然数a，b互质，则不能表示成ax+by（x，y为非负整数）的最大整数是ab-a-b。

证明：见这位大神：https://zhidao.baidu.com/question/305250238.html

由此我们可以知道，若gcd(a, b) == 1, 则从ab-a-b+1开始，所有的数都可以表示成ax+by的形式

所以必然存在区间全白，那么由无限个白，则只有有限个黑