同余方程

扩展欧几里得模板题，求最小正解

python代码

def exGcd(a,b):
    if b == 0:
        return 1,0,a
    x,y,gcd = exGcd(b,a % b)

    return y, x - a // b * y , gcd

#ax + yb = 1
a,b = map(int,input().split())
x,y,gcd = exGcd(a,b)

x = x // gcd * 1
n = b // gcd
print((x%n+n)%n)