【常用算法总结——中国剩余定理】

「爱情、让人受尽委屈。」 2021-11-10 08:28 294阅读 0赞

中国剩余定理，又称孙子定理（什么名字啊）是中国古代求解一次同余式组（见同余）的方法。是数论中一个重要定理。首先来一个小！例！题！吧！

注释：三数为a b c，余数分别为 m1 m2 m3，%为求  今年 余计算，&&是“且”运算。 1、分别找出能被两个数整除，而满足被第三个整除余一的最小的数。 k1%b==k1%c==0 && k1%a==1; k2%a==k2%c==0 && k2%b==1; k3%a==k3%b==0 && k3%c==1; 2、将三个未知数乘对应数字的余数再加起来，减去这三个数的最小公倍数的整数倍即得结果。 Answer = k1×m1 + k2×m2 + k3×m3 - P×(a×b×c); P为满足Answer > 0的最大整数； 或者 Answer = (k1×m1 + k2×m2 + k3×m3)%(a×b×c) ;

![1710567-20190725100805877-907435133.png][]

我们来小小的证明一波

设M=m1*m2*......*mn 　　Mi=M/mi 　　设Mi的逆元为Mi^(-1)(mod mi) 　　有Mi*Mi^(-1)≡1(mod mi) 　　ai*Mi*Mi^(-1)≡ai(mod mi) 　　对于所有的j不等于i 　　ai*Mi*Mi^(-1)≡0(mod mj) 　　所以答案就是所有ai*Mi*Mi^(-1)（mod p）的值

[P3868 \[TJOI2009\]猜数字][P3868 _TJOI2009]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 long long x,y;
     4 long long a[15],b[15];
     5 long long n;
     6 void exgcd(long long A,long long B)
     7 {
     8     if(B==0)
     9     {
    10         x=1;
    11         y=0;
    12         return;
    13     }
    14     exgcd(B,A%B);
    15     long long z=x;
    16     x=y;
    17     y=z-(A/B)*y;
    18 }
    19 long long fast(long long a1,long long b1,long long mod)
    20 {
    21     long long ans=0;
    22     a1%=mod;
    23     b1%=mod;
    24     while(b1)
    25     {
    26         if(b1&1)
    27         {
    28             ans=(ans+a1)%mod;
    29         }
    30         b1>>=1;
    31         a1=(a1+a1)%mod;
    32     }
    33     return ans;
    34 }
    35 long long china()
    36 {
    37     long long ans=0;
    38     long long M=1;
    39     for(long long i=1;i<=n;i++)
    40         M*=b[i];
    41     for(long long i=1;i<=n;i++)
    42     {
    43         long long m=M/b[i];
    44         exgcd(m,b[i]);
    45         while(x<0)
    46             x+=b[i]; 
    47         x%=b[i];
    48         ans=(ans+fast(x,fast(m,(a[i]+M)%M,M),M)+M)%M;
    49     }
    50     return ans;
    51 }
    52 int main()
    53 {
    54     cin>>n;
    55     for(long long i=1;i<=n;i++)
    56     {
    57         scanf("%lld",&a[i]);
    58     }
    59     for(long long i=1;i<=n;i++)
    60     {
    61         scanf("%lld",&b[i]);
    62     }
    63     cout<<china();
    64     return 0;
    65 }

转载于:https://www.cnblogs.com/hualian/p/11242504.html

[1710567-20190725100805877-907435133.png]: /images/20211109/d1d75ff0a2d548a7948999000aacb8db.png
[P3868 _TJOI2009]: https://www.luogu.org/problem/P3868