逆元

接下来，我们来学习如何求解线性同余方程。让我们考虑如何求线性方程ax=b(mob m)。对于实数运算下的方程ax=b，由于a存在倒数，因此很容易求解。如果在mod m的运算下，也有像满足ay=1(mob m)这样的a的倒数存在，方程就可以求解了。我们把这样的y叫做a的逆元，记作a^-1。如果能求解逆元，那么就有x=a^-1*xa=a^-1b，也就可以求出x了。由于方程ax=1(mob m)等价于存在整数k使得ax=1+mk，因此稍作变形之后，可以变为求解满足ax-mk=1的x的问题。这个问题可以用extgcd(扩展欧几里得算法)求解。同时，也可以知道如果gcd(a,m)!=1，那么逆元是不存在的。

int mod_inverse(int a,int m){
    int x,y;
    extgcd(a,m,x,y);
    return (m + x % m) % m;
}

如果a和m不互素，那么ax=b(mob m)就等价于
(a/gcd(a,m))x≡b/gcd(a,m)(mob m/gcd(a,m))
从式子中可以看出，当b无法整除gcd(a,m)时，原方程无解。在有解的情况下，我们有
x≡gcd(a/gcd(a,m))^(-1)*(b/gcd(a,m))(mob m/gcd(a,m))
因此，ax=b(mob m)的解为
x≡a(a/gcd(a,m))^(-1)*(b/gcd(a,m))+(m/gcd(a,m))*k(mob m)(0≤k<gcd(a,m))
需要注意的是这里和实数的情况有所不同，有可能有多解，也有可能无解。