• <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)  編輯 收藏 引用 所屬分類: 數學
            99久久国产主播综合精品| 狠狠色丁香久久婷婷综合_中 | 性做久久久久久久久久久| 蜜臀久久99精品久久久久久| 久久天天躁夜夜躁狠狠| .精品久久久麻豆国产精品| 久久国产三级无码一区二区| 色欲久久久天天天综合网| 精品一区二区久久久久久久网站| 国内精品免费久久影院| 久久亚洲国产最新网站| 中文字幕亚洲综合久久| 亚洲中文字幕无码久久2017 | 91视频国产91久久久| 久久久久99精品成人片牛牛影视| 久久精品夜夜夜夜夜久久| 亚洲欧美精品一区久久中文字幕| 韩国无遮挡三级久久| 伊人久久精品无码av一区| 久久香蕉国产线看观看猫咪?v| 久久久精品2019免费观看| 97视频久久久| 亚洲精品第一综合99久久| 久久国产成人亚洲精品影院| 成人国内精品久久久久影院| 久久久久人妻一区二区三区| 伊人色综合久久天天网| 久久午夜无码鲁丝片午夜精品| 99久久精品九九亚洲精品| 韩国三级大全久久网站| 99麻豆久久久国产精品免费| 久久精品国产99久久无毒不卡 | 国产精品成人久久久| 久久国产精品国语对白| 91精品婷婷国产综合久久| 久久99国产精一区二区三区| 狠狠色婷婷综合天天久久丁香 | 久久最新精品国产| 久久国产精品99久久久久久老狼 | 久久国产精品国产自线拍免费| …久久精品99久久香蕉国产 |