python解mx=y modn

这是一个线性同余方程，可以使用扩展欧几里得算法来求解。

首先，求出mx和n的最大公约数gcd(m,n)，如果gcd(m,n)不整除y，那么方程无解。如果gcd(m,n)整除y，则可以将方程化为：

mx + ny = gcd(m,n)

由于gcd(m,n)|m，因此可以将方程简化为：

(m/gcd(m,n))x + (n/gcd(m,n))y = 1

然后，使用扩展欧几里得算法求解上述方程，得到x的值即为解。具体实现可以参考下面的代码：

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        gcd, x, y = extended_gcd(b, a % b)
        return gcd, y, x - (a // b) * y

def linear_congruence(m, y, n):
    gcd, x, _ = extended_gcd(m, n)
    if y % gcd != 0:
        return None
    else:
        x = (x * (y // gcd)) % n
        return x

其中，extended_gcd函数用于求解扩展欧几里得算法，linear_congruence函数用于求解线性同余方程。