线性同余方程组模板( x=r0(mod m0) )

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
#define N 10100


/*对于x=r0(mod m0)
     x=r1(mod m1)
        ...
     x=rn(mod mn)
输入数组m和数组r，返回[0,[m0,m1,...,mn]-1] 范围内满足以上等式的x0。
x的所有解为:x0+z*[m0,m1,...mn](z为整数)
*/
long long cal_axb(long long a,long long b,long long mod)
{
    //防乘法溢出
    long long sum=0;
    while(b)
    {
        if(b&1) sum=(sum+a)%mod;
        b>>=1;
        a=(a+a)%mod;
    }
    return sum;
}

//ax + by = gcd(a,b)
//传入固定值a,b.放回 d=gcd(a,b), x , y
void extendgcd(long long a,long long b,long long &d,long long &x,long long &y)
{
    if(b==0){d=a;x=1;y=0;return;}
    extendgcd(b,a%b,d,y,x);
    y -= x*(a/b);
}

long long Multi_ModX(long long m[],long long r[],int n)
{
    long long m0,r0;
    m0=m[0]; r0=r[0];
    for(int i=1;i<n;i++)
    {
        long long m1=m[i],r1=r[i];
        long long k0,k1;
        long long tmpd;
        extendgcd(m0,m1,tmpd,k0,k1);
        if( (r1 - r0)%tmpd!=0 ) return -1;
        k0 *= (r1-r0)/tmpd;
        m1 *= m0/tmpd;
        r0 = ( cal_axb(k0,m0,m1)+r0)%m1;
        m0=m1;
    }
    return (r0%m0+m0)%m0;
}
/*
int main()
{
    int k;
    while(cin>>k)
    {
        long long a[N],r[N];
        for(int i=0;i<k;i++)
            cin>>a[i]>>r[i];
        cout<<Multi_ModX(a,r,k)<<endl;
    }
    return 0;
}
*/