鬼知道我的$exgcd$和谁学的,错了好几次。
主要写一下中国剩余定理(又叫孙子定理)
$CRT:mathfrak {Chinese Remainder Theorem}$
中国剩余定理用于求解同余方程。
但是它的作用不止如此。
一般来说,题目中会友好的给一个质数做模数,用费马小定理切掉!
但是也有嫌题目简单的出题人会给一个合数(由互不相同的质数乘得)
这时我们就可以用中国剩余定理切了它。
后续:
出题人更加毒瘤,把合数出成了:
如:
$1000000200=2×2×2×3×5×5×47×35461$
这时我们又尴尬了,不过也可以拓展。
用$mathsf{EXCRT}$就可以!管他,我又不会~~
好了,正题!
用于求解形如:
egin{cases}x & equiv & ans_1 (mod p_1)\x & equiv & ans_2 (mod p_2) \ & vdots & \x & equiv & ans_n (mod p_n)end{cases}
的毒瘤美好式子。
然后我们可以把每一个同余方程解出来。用$exgcd$,唔,不会这个就善用搜索引擎吧。
把代码丢下:
void exgcd(int a,int b,int &x,int &y) { if(b==0){ x=1; y=0; return;} exgcd(b,a%b,x,y); int tp=x; x=y; y=tp-a/b*y; } int china() { int ans=0,lcm=1,x,y; for(int i=1;i<=k;++i) lcm*=b[i]; for(int i=1;i<=k;++i) { int tp=lcm/b[i]; exgcd(tp,b[i],x,y); x=(x%b[i]+b[i])%b[i];//x要为最小非负整数解 ans=(ans+tp*x*a[i])%lcm; } return (ans+lcm)%lcm; } //--------------------- //作者:niiick //来源:CSDN //原文:https://blog.csdn.net/niiick/article/details/80229217 //版权声明:本文为博主原创文章,转载请附上博文链接!