拓展欧几里得算法

拓展欧几里得算法，写下来怕忘。

代码如下：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<string>
#define ll long long
using namespace std;
ll a[11],m[11];
ll exgcd(ll,ll,ll &,ll &);
ll CRT(ll*,ll*,ll);//ll*表示此处引用一个数组。
int main()
{    
    ll n,i;
    cin>>n;
    for(i=1;i<=n;++i)
       cin>>m[i]>>a[i];
    cout<<CRT(a,m,n)<<endl;
    return 0;
}

ll exgcd(ll a,ll b,ll &x,ll &y)//求不定方程ax+by=gcd(a,b)的程序，背过就好。
{
    if(b==0)//如果b=0，原方程就变成了ax=a
    {
        x=1;y=0;
        return a;
    }
    ll r=exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return r;
}

ll CRT(ll a[],ll m[],ll n)//中国剩余定理，简称CRT。
{
    ll M=1;
    ll ans=0;
    for(ll i=1;i<=n;++i)
       M*=m[i];//求mi的和
    for(ll i=1;i<=n;++i)
    {
        ll x,y;
        ll Mi=M/m[i];//不定方程中x的系数
        exgcd(Mi,m[i],x,y);
        ans=(ans+Mi*a[i]*x)%M;
    }
    if(ans<0) ans+=M;
    return ans;
}

PS：这道题是【洛谷P1495】 曹冲养猪的AC100分代码，是一道很裸的exgcd算法（虽然没有全部搞懂），以后的同余方程就可以这样写了qwq。

还有，在数论题中，尽量用long long，否则容易炸。

还有还有，这个代码的要求是所有模互素。

还有还有还有，emmm，好像没有了