• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            ArcTan

            dfs
            隨筆 - 16, 文章 - 117, 評論 - 6, 引用 - 0
            數據加載中……

            中國剩余定理

            設m1,m2,...,mk是兩兩互素的正整數,對于任意的正整數a1,a2,a3,..,ak 同余方程組:
             x≡a1 (mod m1)
             x≡a2 (mod m2)
             ...
             x≡ak (mod mk)
             必有解, 且解可寫為
             x≡M1N1a1+MkNkak+....MkNkak (mod m)
             其中 m=m1m2m3....mk
             Mi=m/mi,(1<=i<=k)
             Nj滿足MjNj≡1(mod mj),1<=j<=k
            即:
                  Ni,Mi是對模mi的互為逆元。
            http://www.cnblogs.com/walker01/archive/2010/01/23/1654880.html
            這篇寫得不錯哇。
                 
            中國剩余定理O(nlogn),還算高效率的。
            #include<stdio.h>
            #include
            <string.h>
            #include
            <math.h>
            int a[25],m[25],M[25],N[25];
            int gcd_ext(int a,int b,int *x,int *y)
            {
                
            int d,tmp;
                
            if (b==0)
                {
                    
            *x=1;*y=0;
                    
            return a;
                }
                d
            =gcd_ext(b,a%b,x,y);
                tmp
            =*x;*x=*y;*y=tmp-(a/b)**y;
                
            return d;
            }
            long long ChReTheorim(int n)
            {
                
            int i,x,y;
                
            long long ans,mul;
                mul
            =1;
                
            for (i=1;i<=n ;i++ )
                    mul
            *=m[i];
                ans
            =0;
                
            for (i=1;i<=n ;i++ )
                {
                    M[i]
            =mul/m[i];
                    gcd_ext(M[i],m[i],
            &x,&y);
                    N[i]
            =(x+m[i])%m[i];
                    ans
            =(ans+a[i]*M[i]*N[i]) % mul;
                }
                
            return ans;
            }

            int main()
            {
                
            int i,n;
                
            long long ans;
                
            while (scanf("%d",&n)==1)
                {
                    mul
            =1;
                    
            for (i=1;i<=n ;i++ )
                        scanf(
            "%d%d",&a[i],&m[i]);
                    ans
            =ChReTheorim(n);
                    printf(
            "%lld\n",ans);
                }
                
            return 0;
            }
            尼瑪,看算法上的乘法逆元給看成加法逆元了。我還以為我找到O(n)的算法呢。氣死:
               a=a1(mod n1)
               a=a2(mod n2)

               a=(a1*n2*N2+a2*n1*N1) % (n1*n2)
            其中
               N1是n1模n2的逆元,N2是n2模n1的逆元。
            如此反復迭代,可求解。

            long long TongYu(int a1,int n1,int a2,int n2)
            {
                
            int N1,N2,x,y,ans;
                gcd_ext(n1,n2,
            &x,&y);
                N1
            =(n2+x) % n2;
                gcd_ext(n2,n1,
            &x,&y);
                N2
            =(n1+x) % n1;
                printf(
            "%d %d\n",N1,N2);
                ans
            =(a1*n2*N2+a2*n1*N1) % (n1*n2);
                
            return ans;
            }
            哦,



            posted on 2012-04-30 16:34 wangs 閱讀(279) 評論(0)  編輯 收藏 引用 所屬分類: ACM-數學

            久久青青国产| 国产成人久久精品一区二区三区| 日本久久久精品中文字幕| 丁香五月综合久久激情| 久久人人超碰精品CAOPOREN| 99久久香蕉国产线看观香 | 国产Av激情久久无码天堂| 久久香蕉综合色一综合色88| 久久久久亚洲?V成人无码| 性欧美大战久久久久久久久| 亚洲乱亚洲乱淫久久| 精品国产青草久久久久福利| 久久精品无码专区免费青青| 久久久久久久国产免费看| 亚洲AV无码1区2区久久| 久久精品国产色蜜蜜麻豆| 亚洲女久久久噜噜噜熟女| 国产日韩欧美久久| 久久av无码专区亚洲av桃花岛| 国产精品青草久久久久福利99| 亚洲精品tv久久久久久久久 | 久久久不卡国产精品一区二区| 国产成人无码精品久久久性色| 久久99热精品| 久久久久亚洲av无码专区| 国产99久久久国产精品小说| 国产L精品国产亚洲区久久| 久久久久久无码Av成人影院| 亚洲精品国精品久久99热| 久久精品国产WWW456C0M| 久久久久四虎国产精品| 午夜精品久久久久久99热| 久久久www免费人成精品| 香蕉99久久国产综合精品宅男自 | 亚洲精品无码久久毛片| 成人a毛片久久免费播放| 91久久婷婷国产综合精品青草| 亚洲中文字幕无码一久久区| 久久精品国产亚洲AV忘忧草18 | 久久精品国产亚洲AV麻豆网站| 久久免费看黄a级毛片|