如果有相应的OJ题目,欢迎同学们提供相应的链接

相关链接

• 所有模板的快速链接
• 扩展欧几里得extend_gcd模板
• poj_1006_Biorhythms,my_ac_code

简单的测试

None

代码模板

/*

 * TIME COMPLEXITY:O(nlogm)

 * PARAMS:

 *      a       x==ai(mod mi)

 *      m

 *      n       the number of equation.

 */

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;

}