• <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>
            心如止水
            Je n'ai pas le temps
            posts - 400,comments - 130,trackbacks - 0
            題目大意:判斷一個數字n是不是Carmichael number,所謂Carmichael number,滿足兩個條件:是合數;對于任意a(2<=a<=n-1),都有a^n mod n=a。
            只需要預處理篩素數和了解快速冪取模即可。
            以下是我的代碼:
            #include<stdio.h>
            #include
            <math.h>
            const long maxn=65007;
            bool isPrime[maxn];
            void get_prime()
            {
                
            long Prime[maxn],tot;
                
            for(long i=1;i<maxn;i++) isPrime[i]=true;
                isPrime[
            1]=false;
                tot
            =0;
                
            for(long i=2;i<maxn;i++)
                {
                   
            if(isPrime[i])
                   {
                      tot
            ++;Prime[tot]=i;
                   }
                   
            for(long j=1;j<=tot&&i*Prime[j]<maxn;j++)
                   {
                      isPrime[i
            *Prime[j]]=false;
                      
            if(i%Prime[j]==0break;
                   }
                }
            }
            long mod(long a,long n,long b)
            {
                
            if(n==1return a%b;
                
            long ans=mod(a,n/2,b);
                ans
            =(ans*ans)%b;
                
            if(n%2==1return ans*a%b;
                
            return ans;
            }
            bool check(long n)
            {
                
            for(long i=2;i<=n-1;i++)
                  
            if(mod(i,n,n)!=i)
                    
            return false;
                
            return true;
            }
            int main()
            {
                
            /*
                freopen("data.in","r",stdin);
                freopen("data.out","w",stdout);
                //
            */
                
            long n;
                get_prime();
                
            while(scanf("%ld",&n)==1)
                {
                   
            if(n==0break;
                   
            if(!isPrime[n]&&check(n))
                     printf(
            "The number %ld is a Carmichael number.\n",n);
                   
            else printf("%ld is normal.\n",n);
                }
            return 0;
            }


            posted on 2010-01-23 19:56 lee1r 閱讀(1009) 評論(0)  編輯 收藏 引用 所屬分類: 題目分類:數學/數論
            国产精品久久久久蜜芽| 91精品国产91久久综合| 久久精品国产免费| 97久久国产亚洲精品超碰热 | 久久午夜福利无码1000合集| 久久久久18| 久久这里都是精品| 久久婷婷五月综合97色直播| 久久精品国产AV一区二区三区 | 亚洲国产欧洲综合997久久| 色综合合久久天天给综看| 日批日出水久久亚洲精品tv| 亚洲精品无码久久久久AV麻豆| 无码乱码观看精品久久| 狠狠色婷婷久久一区二区| 亚洲va久久久噜噜噜久久| 久久成人国产精品| 久久伊人亚洲AV无码网站| 亚洲国产精品成人久久| 亚洲国产精品久久久久婷婷软件| 免费一级欧美大片久久网 | 久久久久AV综合网成人 | 久久精品一区二区影院| 久久亚洲AV无码精品色午夜| 国产欧美一区二区久久| 一本色道久久综合狠狠躁篇| 狠色狠色狠狠色综合久久| 2021国内久久精品| 久久久精品波多野结衣| 久久99国产乱子伦精品免费| 国产高潮久久免费观看| 久久狠狠高潮亚洲精品| 国产精品久久久久久久人人看 | 久久精品国产99国产精偷 | 国产∨亚洲V天堂无码久久久| 亚洲国产成人精品久久久国产成人一区二区三区综| 久久人人青草97香蕉| 久久精品无码一区二区app| 青青草原综合久久大伊人精品| 久久久久久精品免费看SSS| 午夜福利91久久福利|