题解 | #猫猫与数学#

思路：让 $a+c$ 和 $b+c$ 有共同质因子；任何共同质因子必整除 $d=|a-b|$ ，所以枚举 $d$ 的质因子 $p$ ，取最小的 $c$ 使 $a+c \equiv 0 \pmod{p}$ 。

证明：若 $g \mid a+c$ 且 $g \mid b+c$ ，则 $g \mid (b-a)=d$ ，所以这样的 $g$ 必为 $d$ 的因子；反之取 $p \mid d$ 并令 $c\equiv -a \pmod{p}$ 即可使 $p$ 同时整除 $a+c$ 和 $b+c$ ，若 $d=1$ 则无解。

import sys
data=sys.stdin.read().split()
it=iter(data)

MOD=1e9+7
MOD2=998244353
def solve():
    a,b=int(next(it)),int(next(it))
    if a==b:
        if a==1:
            print(1)
            return
        else:
            print(0)
            return
    d=abs(a-b)
    s=int(d**0.5)
    ans=10**30
    for i in range(2,s+1):
        if d%i==0:
            g1=i
            c=(g1-a%g1)%g1
            if c<ans:
                ans=c
            g2=d//i
            if g2>1:
                c=(g2-a%g2)%g2
                if c<ans:
                    ans=c
    if d>1:
        c=(d-a%d)%d
        if c<ans:
            ans=c
    if ans==10**30:
        print(-1)
    else:
        print(ans)

if __name__=="__main__":
    _=1
    #_=int(next(it))
    for __ in range(_):
        solve()