题解 | 猫猫与数学

from math import gcd

a, b = map(int, input().split())
inf = float("inf")

if gcd(a, b) > 1:
    print(0)
elif a & 1 and b & 1:
    print(1)
elif a == b:
    if a == 1:
        print(1)
    else:
        print(0)
elif abs(a - b) == 1:
    print(-1)
else:
    ans = inf
    temp = abs(a - b)
    p = 2
    while p * p <= temp:
        if temp % p == 0:
            c = (p - (a % p)) % p
            ans = min(ans, c)
            while temp % p == 0:
                temp //= p
        p += 1 if p == 2 else 2
    if temp > 1:
        c = (temp - (a % temp)) % temp
        ans = min(ans, c)

    if ans == inf:
        print(-1)
    else:
        print(ans)

为了使得 gcd⁡(a+c,b+c)≠1

可以分几种情况

1.gcd(a,b)已经>=1,直接输出0

2.a&1 and b&1,a和b都是奇数，+1即可都是偶数

3.a和b相差1，永远不可能

4.a==b，因为gcd(a,b)==a 所有只要a不是1，输出0，否则输出1

5其余情况枚举计算

需要一个c使得gcd⁡(a+c,b+c)≠1,

我们假设gcd⁡(a+c,b+c)≠1,

那么一定存在一个质数p使得a+c和b+c可以被整除即p∣(a+c)且p∣(b+c)

如果 p同时整除 a+c和 b+c，那么它也整除它们的差：

p∣[(a+c)−(b+c)]=p∣a−b

记 t=a−b（取绝对值，符号不影响整除性），所以：

p∣t

关键结论：公共质因子 p一定是 t的质因子

由 p∣(a+c)得：

a+c≡0(mod p)

c≡−a(mod p) 

最小非负解是：

c=(p−(a mod p))mod p 解同余方程自行搜索

我们对每个质因子 p 算出一个 c，然后取所有 c 中的最小值，就是答案