首页 > 代码库 > 模板——中国剩余定理

模板——中国剩余定理

 1 //n个方程,x=a[i](mod m[i])  2  3 LL china(int n, int  *a, int *m) { 4     LL M = 1, d, y, x = 0; 5     for(int i = 0; i < n; i++) M *= m[i]; 6     for(int i = 0; i < n i++) { 7         LL w = M / m[i]; 8         exgcd(m[i], w, d, d, y); 9         x = (x + y*w*a[i]) % M;10     }11     return (x + M) % M;12 }

 

模板——中国剩余定理