• <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>
            隨筆 - 87  文章 - 279  trackbacks - 0
            <2007年10月>
            30123456
            78910111213
            14151617181920
            21222324252627
            28293031123
            45678910

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217839
            • 排名 - 117

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            歐拉函數(shù)一般形式:
            當(dāng) n 為素?cái)?shù)時(shí): phi(n) = n-1
            當(dāng) n 為合數(shù)時(shí): phi(n) = n∏(1-1/p) 其中(p為n的素?cái)?shù)因子)

            題目pku1091,要求我們求 x1..xn,m這樣的序列的個(gè)數(shù),其中xi(1<=i<=n), 使 gcd(x1, ..,xn,m)=1;
            我們按歐拉函數(shù)的形式猜想如下方程:
            當(dāng) n 為素?cái)?shù)時(shí): phi(m,n) = m^n-1
            當(dāng) n 為合數(shù)時(shí): phi(m,n) = m^n∏(1-1/p^n) 其中(p為n的素?cái)?shù)因子)

            不給出嚴(yán)格數(shù)學(xué)證明(不會(huì)-_-),上兩式具體含義:
            當(dāng) n為素?cái)?shù) phi(m,n) = m^n-1 顯然成立
            當(dāng) n 為合數(shù)時(shí) 可以假象有一個(gè)m進(jìn)制n位的數(shù),然后其中一位有m的約數(shù)p的概率為1/p, 則n位同時(shí)有p的約數(shù)的概率就為(1-1/p^n), 運(yùn)用乘法原理,可以得式 phi(m,n) = m^n∏(1-1/p^n)
             
            code:

            #include <iostream>
            using namespace std;

            typedef __int64 llong;
            const llong MAXN = 110000;
            llong tf[MAXN], su[MAXN], ns, num[MAXN], nn;

            void  init() {
                llong i, j;
                
            for (i=2; i<MAXN; i++) {
                    
            if (!tf[i]) {
                        su[ns
            ++]=i;
                        
            for (j=i*i; j<MAXN; j+=i) tf[j]=1;
                    }
                }
            }

            llong ppow(llong a, llong b) {
                llong ret
            =a;
                llong i;
                
            for (i=1; i<b; i++) ret *= a;
                return ret;
            }

            int main() {
                llong n, m, i, p;
                llong ans
            =0;
                init();
                
            while (scanf("%I64d%I64d"&n, &m)!=EOF) {
                    p
            =m; nn=0; ans=0;
                    
            for (i=0; i<ns; i++) {
                        
            if (p%su[i]==0) {
                            
            while (p%su[i]==0) p/=su[i];
                            num[nn
            ++]=su[i];
                        }
                        
            if (p==1) break;
                    }
                    
            if (!nn) {
                        ans 
            = ppow(m,n)-1;
                    } 
            else {
                        ans 
            = ppow(m,n);
                        
            for (i=0; i<nn; i++) {
                            ans 
            = ans/ppow(num[i],n)*(ppow(num[i],n)-1);
                        }
                    }
                    printf(
            "%I64d\n", ans);
                }
                return 
            0;
            }
            posted on 2007-09-02 22:57 閱讀(2502) 評(píng)論(4)  編輯 收藏 引用 所屬分類: 算法&ACM

            FeedBack:
            # re: 擴(kuò)展的歐拉函數(shù) pku1091 2007-09-18 09:41 nice
            這個(gè)公式好牛,類比的好強(qiáng)  回復(fù)  更多評(píng)論
              
            # re: 擴(kuò)展的歐拉函數(shù) pku1091[未登錄] 2007-10-07 10:35 beyond
            你好,常來你個(gè)Blog,故對(duì)你的網(wǎng)名很熟悉,近日在NUAA( Latin Stones 1110 )上看你做了一題歐拉定理得題,那題我沒有i想法,能把遞推公式還有代碼發(fā)給我,供學(xué)習(xí)參考嗎?非常感謝!我的郵箱是:beyondjjj@tom.com  回復(fù)  更多評(píng)論
              
            # re: 擴(kuò)展的歐拉函數(shù) pku1091 2007-10-07 20:43 
            @beyond
            -_-這題不會(huì),我那時(shí)候想dp結(jié)果發(fā)現(xiàn)不行。。。  回復(fù)  更多評(píng)論
              
            # re: 擴(kuò)展的歐拉函數(shù) pku1091 2008-05-28 18:04 maik
            你上面的講解跟程序有出入哦...
            上面應(yīng)該是判斷m是否為素?cái)?shù),且p應(yīng)該是m的因子  回復(fù)  更多評(píng)論
              
            色婷婷噜噜久久国产精品12p| 色天使久久综合网天天| 国内精品伊人久久久久av一坑| 久久青青草原精品国产| 国产成人无码精品久久久久免费 | 91精品国产综合久久婷婷| 久久精品国产亚洲网站| 欧美与黑人午夜性猛交久久久| 99精品国产综合久久久久五月天| 精品一区二区久久| 久久久久人妻一区二区三区| 国产精品久久久久乳精品爆| 久久SE精品一区二区| 精品人妻伦一二三区久久| 精品少妇人妻av无码久久| 日本精品久久久久影院日本| 女人香蕉久久**毛片精品| 亚洲国产视频久久| 久久亚洲精品无码播放| 免费精品99久久国产综合精品| 亚洲中文字幕久久精品无码喷水| 久久精品?ⅴ无码中文字幕| 69国产成人综合久久精品| 精品久久人人爽天天玩人人妻 | 污污内射久久一区二区欧美日韩 | 久久亚洲精品视频| 亚洲国产精品热久久| 一极黄色视频久久网站| 精品熟女少妇av免费久久| 久久久久久综合网天天| 久久播电影网| 精品国产91久久久久久久| 精品熟女少妇av免费久久| 久久精品国产亚洲av麻豆小说 | 久久亚洲熟女cc98cm| 午夜精品久久久久久| 久久露脸国产精品| 人人狠狠综合久久亚洲| 亚洲欧洲中文日韩久久AV乱码| 欧美一区二区久久精品| 欧美精品九九99久久在观看|