线性同余方程

形如 (axequiv b(mod n)) 的方程称为线性同余方程，从区间 ([0,n-1]) 中求解 (x).

逆元求解。

假设 (gcd(a,n)=1)，两边同时乘上 (a^{-1}) 即可。

设 (g=gcd(a,n))，左侧始终可以 被 (g) 整除，若右侧不可则无解。

若右侧可以被 (g) 整除，则将 (a,b,n) 同时除以 (g)，得到 (a'xequiv b'(mod n')).

此时 (gcd(a',n')=1)，回到上面的情况。

所以解为 (xequiv x'+i*n'(mod n),iin[0,g-1])，个数为 (g) 个或 (0) 个。

扩展欧几里得算法求解。

方程可以写成 (ax+nk= b)，有解的充要条件是 (gcd(a,n)|b).

先算出 (ax_0+nk_0=gcd(a,n))，之后两边同时除以 (gcd(a,n)) 再乘上 (b) 即为一组解。

即 (a=frac{x_0}{gcd(a,n)}b,k=frac{k_0}{gcd(a,n)}b).

若 (gcd(a,n)=1,ax+nk=b) 的一组特解为 (x_0,k_0)，则任意解可以写成 (x=x_0+nt,k=k_0-at,t) 为任意整数。

对于求一个最小整数解，(x=(xmod t+t)mod t,t=frac{n}{gcd(a,n)})

https://www.luogu.com.cn/problem/P2613

给定 (a,b,p)，求 (c=frac{a}{b}(mod p),0<=a<=10^{10001},1<=b<=10^{10001}).

读入过大，但是是同余方程，可以在读入时将其进行取模，当 (b) 是 (p) 的倍数时不存在逆元，分母为零，无解。

constexpr int N=5e6+6,mod=19260817;
template<class T>inline T readmod(T&x){
    char c=getchar();x=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),x%=mod,c=getchar();
    return x;
}
signed main(){
    int a,b,x,y;
    readmod(a),readmod(b);
    if(b==0){
        cout<<"Angry!";
        return 0;
    }
    exgcd(b,mod,x,y);
    x=(x%mod+mod)%mod;
    cout<<a*x%mod;
    return 0;
}