[关闭]
@xzyxzy 2018-07-03T12:01:29.000000Z 字数 1684 阅读 579

中国剩余定理(CRT)

数学

作业部落

评论地址


一、对于一系列同余方程的求解


先考虑两项的情况
先假设
为其一解,则有
那么会有方程
运用扩展欧几里得求得一解
则可以得以及


个依次合并可得结果

可以看作加上对式子没有影响,那么的时候就加(最小公倍数)就好了
最终

二、举例

孙子算经:今有物不知其数,三三数之余二,无物数之余三,七七数之余二,问物几何?


由前两式列得方程

列得方程
从而得出
例题:韩信点兵

三、用途

可以处理这种同余方程
也可以处理任意模数NTT

Code

注意我的代码和网上绝大部分博主的不一样
大部分人是把同余方程拆开,像数学一本通上面做的那样
而我的就是在模拟上面说的过程
其中调试了很久,原因在于我的乘法可能会乘爆
加上函数就好啦(我也不知道为什么,哪位dalao可以告诉我原理>_<)

  1. //COGS1786 韩信点兵
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #define ll long long
  6. using namespace std;
  7. ll N,m,P[11],a[11];
  8. ll mul(ll x,ll y,ll m)
  9. {
  10. x%=m;y%=m;
  11. return (x*y-(ll)((long double)x/m*y+0.5)*m+m)%m;
  12. }
  13. void Exgcd(ll a,ll b,ll &x,ll &y)
  14. {
  15. if(!b){x=a;y=0;return;}
  16. Exgcd(b,a%b,y,x);y-=a/b*x;
  17. }
  18. void CRT()
  19. {
  20. ll x,y,c;
  21. for(int i=2;i<=m;i++)
  22. {
  23. Exgcd(P[i-1],-P[i],x,y);
  24. c=a[i]-a[i-1];
  25. P[i]=P[i-1]*P[i];
  26. a[i]=((a[i-1]+mul(mul(x,c,P[i]),P[i-1],P[i]))%P[i]+P[i])%P[i];
  27. }
  28. while(a[m]+P[m]<=N) a[m]+=P[m];
  29. if(a[m]>N) puts("-1");
  30. else printf("%lld\n",N-a[m]);
  31. }
  32. int main()
  33. {
  34. freopen("HanXin.in","r",stdin);
  35. freopen("HanXin.out","w",stdout);
  36. cin>>N>>m;
  37. for(int i=1;i<=m;i++)
  38. cin>>P[i]>>a[i];
  39. CRT();
  40. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注