• <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>
            http://acm.hdu.edu.cn/showproblem.php?pid=1787

            /***
            count the number of the integers M (0<M<N) which satisfies gcd(N,M)>1.
            即:N - 1 - phi(N)
              
            由于1<N<100000000, 不肯能預處理所有的歐拉函數
            采用歐拉性質:
                1.若n是質數p的k次冪,φ(n)= (p-1)p^(k-1)
                2.若m,n互質,φ(mn)= φ(m)φ(n)

            若 n =p1^a1 * p2^a2 ** pn^an
            則   phi(n)    = (p1-1)*p1^(a1-1) * (p2-1)*p2^(a2-1) ** (pn-1)*pn^(an-1)
                        = N * (p1-1)*(p2-2)**(pn-1)/(p1*p2**pn)
            *
            */

            #include 
            <stdio.h>
            #define N 10001
            __int64 p[
            5000];
            int hash[10001];
            int main()
            {
                __int64 i, j, ans, n, m, temp;
                
                p[
            0= 1//記錄素數個數
                p[1= 2;
                
            for (i=3; i<N; i+=2)
                {
                    
            if (hash[i])
                        
            continue;
                    p[
            ++p[0]] = i;
                    
            for (j=i*i; j<N; j+=i)
                        hash[j] 
            = 1;
                } 
            //篩素數    
                
                
                
            while (scanf("%I64d"&n), n)
                {        
                    ans 
            = 1;
                    m 
            = n;        
                    
            for (i=1; p[i]<=&& i<=p[0]; i++)
                        
            if (m%p[i]==0)
                        {
                            temp 
            = 1;
                            
            while (m%p[i] == 0)
                            {
                                m 
            /= p[i];
                                temp 
            *= p[i];
                            }
                            temp 
            /= p[i];
                            ans
            *=(p[i]-1)*temp;
                        }
                    
            if (m>1)
                    {
                        ans 
            *= (m-1);
                    }    
            //如果剩下那個數大于1,m為大于10000的質數
                    
                    printf(
            "%I64d\n", n-ans-1);
                }



            posted on 2009-12-02 20:34 西風蕭瑟 閱讀(984) 評論(0)  編輯 收藏 引用 所屬分類: 數學
            精品免费tv久久久久久久| 久久午夜电影网| AV无码久久久久不卡蜜桃| 久久这里只有精品18| 久久精品国产影库免费看| 久久精品免费全国观看国产| 国产精品99久久99久久久| 91秦先生久久久久久久| 无码人妻久久久一区二区三区| 国产99久久久国产精品~~牛| 久久精品国产亚洲AV蜜臀色欲| 办公室久久精品| 成人综合伊人五月婷久久| 精品久久久久久无码不卡| 国产精品xxxx国产喷水亚洲国产精品无码久久一区 | 精品人妻伦九区久久AAA片69| 久久久久亚洲国产| 久久精品国产一区二区三区| 精品九九久久国内精品| 亚洲AV日韩精品久久久久久久| 亚洲精品无码久久毛片| 国产激情久久久久影院小草| 97r久久精品国产99国产精| 色诱久久久久综合网ywww| 欧美午夜A∨大片久久| 国产精品免费久久久久久久久| 高清免费久久午夜精品| 久久久老熟女一区二区三区| 午夜精品久久久久久99热| 日韩乱码人妻无码中文字幕久久| 久久久久久精品无码人妻| 久久人人爽人人人人爽AV| 亚洲精品无码久久久| 久久久久久久波多野结衣高潮| 免费一级做a爰片久久毛片潮| 国内精品久久久久久久涩爱| 国产精品热久久无码av| 久久综合成人网| 色妞色综合久久夜夜| 人妻精品久久无码专区精东影业| 亚洲午夜久久久影院伊人|