扩展中国剩余定理(模板)

证明：挂个大佬的博客：点击查看

挂上代码供以后白嫖：

LL n,m[N],a[N];///模数为m,余数为a, X % m = aLL extend_gcd(LL a,LL b,LL &x,LL &y) {if(b==0){x=1,y=0;return a;}else{LL x1,y1;LL d = extend_gcd(b,a%b,x1,y1);x = y1;y = x1-a/b*y1;return d;} }bool solve(LL &m0,LL &a0,LL m,LL a) {long long y,x;LL g = extend_gcd(m0,m,x,y);LL t = a-a0>0?a-a0:a0-a;if( t%g )return false;x *= (a - a0)/g;x %= m/g;a0 = (x*m0 + a0);m0 *= m/g;a0 %= m0;if( a0 < 0 )a0 += m0;return true; } /** * 无解返回false,有解返回true; * 解的形式最后为 a0 + m0 * t (0<=a0<m0) */ bool MLES(LL &m0 ,LL &a0)///解为 X = a0 + m0 * k {bool flag = true;m0 = 1;a0 = 0;for(int i = 0; i < n; i++)if( !solve(m0,a0,m[i],a[i]) ){flag = false;break;}return flag; }

 

总结

以上是生活随笔为你收集整理的扩展中国剩余定理(模板)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。