中国剩余定理-白红宇

中国剩余定理

阅读量：4518 次

发布时间：2019-06-08

本文共 1333 字，大约阅读时间需要 4 分钟。

中国剩余定理用于求解 x≡ai(mod mi),当中mi两两互质，x有唯一解。

令M为mi的乘积，wi = M/mi,wi关于模mi的逆元为pi,即满足wi*pi + mi*qi = 1.

则上述方程组等价于 x≡ w1*p1*a1 + w2*p2*a2 +......+wk*pk*ak（mod M）................................................................①

验证：当M = m1时，（w2*p2*a2 +......+wk*pk*ak）%m1 = 0，那么上式变为 x≡w1*p1*a1(mod m1)，又由于w1的关于模m1的逆元是p1，那么进一步化简为x≡a1(mod m1)。

类比当M = m2,m3,,,,mk时。①式都是成立的。

因此求x,仅仅需求w1*p1*a1 + w2*p2*a2 +......+wk*pk*ak（mod M），当中wi,ai是已知的，pi可依据方程wi*pi + mi * qi = 1用扩展欧几里得求出。

#include 
     
      #include 
      #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #define LL long long#define _LL __int64using namespace std;LL extend_gcd(LL a, LL b, LL &x, LL &y){ if(b == 0) { x = 1; y = 0; return a; } LL d = extend_gcd(b,a%b,x,y); LL t = x; x = y; y = t - a/b*y; return d;}LL CRT(LL *p, LL *o, int num){ LL x,y; LL ans = 0,n = 1; for(int i = 0; i < num; i++) n *= o[i]; for(int i = 0; i < num; i++) { extend_gcd(n/o[i],o[i],x,y); x = (x + o[i])%o[i]; ans = (ans + n/o[i]*x*p[i])%n; } return ans;}int main(){ int n; LL a[15],m[15]; while(~scanf("%d",&n)) { for(int i = 0; i < n; i++) scanf("%lld %lld",&a[i],&m[i]); printf("%lld\n",CRT(a,m,n)); } return 0;}

转载于:https://www.cnblogs.com/blfshiye/p/5080774.html

你可能感兴趣的文章