中国剩余定理

[UNICKCHENG]

［任务］ 求出方程x≡a_i(mod m_i) (0<=i<n)的解x，其中m₁,m₂,...,m_n-1两两互质

int CRT(int a[],int m[],int n)
{
    int M=1;
    for(int i=0;i<n;i++) M*=m[i];
    int ret=0;
    for(int i=0;i<n;i++)
    {
        int x,y;
        int tm=M/m[i];
        extend_gcd(tm,m[i],x,y);
        ret=(ret+tm*x*a[i])%M;
    }
    return (ret+M)%M;
}

• 扩展欧几里得
• 中国剩余定理定义

待完善