扩欧板子+中国剩余定理板子

关于扩欧：

这个板子我不想再记不住了，所以我推一遍

求解 ax+by = c;

裴蜀定理 ： ax+by=gcd(a,b)一定有解

所以如果 c%gcd！=0 则一定无解

同乘以 d/c  a(d/c*x)+b(d/c*y)=d;

求解的 答案乘上 c/d 就是原来的答案

由 欧几里得 可以得到

(b)x+(a%b)y==gcd(b,a%b)

a%b=a-(a/b)*b

根据多项式的准则

ax+by=d

所以 x=y

y=x-(a/b)*y

注意应写成 ex_gcd（b,a%b,y,x）//x=y

y=x-(a/b)*y

好了上板子

code:

ll ex_gcd(ll a,ll b ,ll &x,ll &y)
{
    if(b==0)
    {
        x=1;
        y=0;
    }
    else
    {
        ex_gcd(b,a%b,y,x);
        y=y-(a/b)*x;
    }
    return x;
}

中国剩余定理:

最小整数解:

x = （a1*M1*inv（M1） + a2 * M2 * inv（M2） + .... + ai * Mi * inv（Mi） + ... + ak*Mk*inv（Mk））%M;

其中：Mi = M/mi ; inv（Mi） 为 Mi 模 mi 的逆元。

求逆_>欧几里得扩展 就好了

费马小定理 的模数必须为质数