中国剩余定理

互质

 ll m[N],p[N];//p是质数，m是余数

ll Exgcd(ll a,ll b,ll &x,ll &y)

{

    if(b==0)

    {

        x=1;

        y=0;

        return a;

    }

    ll x1,y1;

    ll d=Exgcd(b,a%b,x1,y1);

    x=y1;

    y=x1-a/b*y1;

    return d;

}

ll Crt(ll *m,ll *p,int l)

{

    ll res=0,n=1,x,y;

    for(int i=0;i

        n*=p[i];

    for(int i=0;i

    {

        ll t=n/p[i];

        ll d=Exgcd(t,p[i],x,y);

        res=(res+m[i]*t%n*x%n)%n;

    }

    return (res%n+n)%n;

}

非互质

#include//*m模数 *a余数

#include

#include

#include

#include

using namespace std;

typedef long long ll;

void exgcd(ll a,ll b,ll &x,ll &y)

{

    if(!b)

    {

        x=1;y=0;return ;

    }

    exgcd(b,a%b,x,y);

    ll temp=x;

    x=y;y=temp-(a/b)*y;

}

ll inv(ll a,ll b)

{

    ll d=__gcd(a,b);

    if(d!=1)return -1;

    ll x,y;

    exgcd(a,b,x,y);

    return (x%b+b)%b;

}

bool merge(ll a1,ll m1,ll a2,ll m2,ll &a3,ll &m3)

{

    ll d=__gcd(m1,m2);

    ll c=a2-a1;

    if(c%d)return false;

    c=(c%m2+m2)%m2;

    m1/=d;m2/=d;c/=d;

    c*=inv(m1,m2);c%=m2;

    c*=m1*d;

    c+=a1;m3=m1*m2*d;

    a3=(c%m3+m3)%m3;

    return true;

}

ll CRT(ll *a,ll *m,ll n)

{

    ll a1=a[1],m1=m[1];

    for(ll i=2;i<=n;i++)

    {

        ll a2=a[i],m2=m[i];

        ll m3,a3;

        if(!merge(a1,m1,a2,m2,a3,m3))

        return -1;

        a1=a3;m1=m3;

    }

    return (a1%m1+m1)%m1;

}

©著作权归作者所有：来自51CTO博客作者qinXpeng的原创作品，如需转载，请注明出处，否则将追究法律责任