• <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>
            

    
            

            




            







												


        


            


            coreBugZJ
            

            此 blog 已棄。
            

            




            
	
					
	
            
		
            
			POJ 3604 Professor Ben
		
            
		
              1/*
              2POJ 3604 Professor Ben
              3
              4
              5----問題描述：
              6
              7Professor Ben is an old stubborn man teaching mathematics in a university. He likes to puzzle his students with perplexing (sometimes boring) problems. Today his task is: for a given integer N, a1,a2,  ,an are the factors of N, let bi be the number of factors of ai, your job is to find the sum of cubes of all bi. Looking at the confused faces of his students, Prof. Ben explains it with a satisfied smile:
              8
              9Let's assume N = 4. Then it has three factors 1, 2, and 4. Their numbers of factors are 1, 2 and 3 respectively. So the sum is 1 plus 8 plus 27 which equals 36. So 36 is the answer for N = 4.
             10
             11Given an integer N, your task is to find the answer.
             12
             13
             14----輸入：
             15
             16The first line contains the number the test cases, Q(1 ≤ Q ≤ 500000). Each test case contains an integer N(1 ≤ N ≤ 5000000)
             17
             18
             19----輸出：
             20
             21For each test case output the answer in a separate line.
             22
             23
             24----樣例輸入：
             25
             261
             274
             28
             29
             30----樣例輸出：
             31
             3236
             33
             34
             35----分析：
             36
             37由算術基本定理，
             38
             39設 N 有 k 個質因子 P1, P2, . , Pk
             40則
             41N = P1^A1 + P2^A2 + . + Pk^Ak
             42
             43設 N 有 m 個因子 F1, F2, . , Fm
             44則
             45Fj = P1^B1j + P2^B2j + . + Pk^Bkj    (0 <= Bij <= Ai)
             46對任意 Fx 和 Fy，當 x != y 時，必存在 r 使 Brx != Bry
             47
             48則 Fj 的因子數
             49Sj = (1+B1j) * (1+B2j) * . * (1+Bkj)
             50
             51則最終結果
             52ANS = S1^3 + S2^3 + . + Sm^3
             53    = (1+B11)^3 * (1+B21)^3 * . * (1+Bk1)^3 + 
             54      (1+B12)^3 * (1+B22)^3 * . * (1+Bk2)^3 + 
             55      . +
             56      (1+B1m)^3 * (1+B2m)^3 * . * (1+Bkm)^3
             57      其中  Bxy = 0, 1, 2, . , Ax
             58
             59合并同類項
             60ANS = (1^3 + 2^3 + . + (1+A1)^3) * 
             61      (1^3 + 2^3 + . + (1+A2)^3) * 
             62      . * 
             63      (1^3 + 2^3 + . + (1+Ak)^3)
             64
             65*/
             66
             67
             68/**********************************************
             69版本二：
             70
             71*/
             72
             73#include <iostream>
             74#include <cstdio>
             75#include <cstring>
             76
             77using namespace std;
             78
             79typedef  __int64  Lint;
             80
             81#define  N   5000009
             82#define  RN  2240
             83
             84int nprime, prime[ RN ];
             85
             86void init() {
             87        int i, j;
             88        memset( prime, 0, sizeof(prime) );
             89        nprime = 0;
             90        for ( i = 2; i < RN; ++i ) {
             91                if ( 0 == prime[ i ] ) {
             92                        prime[ nprime++ ] = i;
             93                        for ( j = i + i; j < RN; j += i ) {
             94                                prime[ j ] = 1;
             95                        }
             96                }
             97        }
             98}
             99
            100// calc 1^3 + 2^3 + . + (1+a)^3
            101Lint sum( int a ) {
            102        Lint n = a + 1;
            103        Lint h = ( (n&1) ? ((n+1)/2*n) : (n/2*(n+1)) );
            104        return h * h;
            105}
            106
            107Lint solve( int n ) {
            108        int i = -1, p, a;
            109        Lint ans = 1;
            110        while ( 1 != n ) {
            111                do {
            112                        ++i;
            113                }             while ( (i < nprime) && (n % prime[ i ] != 0) );
            114                if ( i >= nprime ) {
            115                        // n 是質數
            116                        a = 1;
            117                        n = 1;
            118                }
            119                else {
            120                        a = 0;
            121                        p = prime[ i ];
            122                        do {
            123                                ++a;
            124                                n /= p;
            125                        }             while ( n % p == 0 );
            126                }
            127                ans *= sum( a );
            128        }
            129        return ans;
            130}
            131
            132int main() {
            133        int td, n;
            134        init();
            135        scanf( "%d", &td );
            136        while ( 0 < td-- ) {
            137                scanf( "%d", &n );
            138                printf( "%I64d\n", solve(n) );
            139        }
            140        return 0;
            141}
            142
            143
            144
            145/**********************************************
            146版本一：
            147TLE
            148*/
            149/*
            150#include <iostream>
            151#include <cstdio>
            152
            153using namespace std;
            154
            155typedef  __int64  Lint;
            156
            157#define  N   5000009
            158#define  RN  2240
            159
            160void init() {
            161}
            162
            163// calc 1^3 + 2^3 + . + (1+a)^3
            164Lint sum( int a ) {
            165        Lint n = a + 1;
            166        Lint h = ( (n&1) ? ((n+1)/2*n) : (n/2*(n+1)) );
            167        return h * h;
            168}
            169
            170Lint solve( int n ) {
            171        int p = 1, a;
            172        Lint ans = 1;
            173        while ( 1 != n ) {
            174                do {
            175                        ++p;
            176                } while ( (p < RN) && (n % p != 0) );
            177                if ( RN <= p ) {
            178                        // n 是質數
            179                        a = 1;
            180                        n = 1;
            181                }
            182                else {
            183                        a = 0;
            184                        do {
            185                                ++a;
            186                                n /= p;
            187                        } while ( n % p == 0 );
            188                }
            189                ans *= sum( a );
            190        }
            191        return ans;
            192}
            193
            194int main() {
            195        int td, n;
            196        init();
            197        scanf( "%d", &td );
            198        while ( 0 < td-- ) {
            199                scanf( "%d", &n );
            200                printf( "%I64d\n", solve(n) );
            201        }
            202        return 0;
            203}
            204*/
            205
            
		
            
			posted on 2012-06-01 21:30 coreBugZJ 閱讀(1740) 評論(1)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、Mathematics 、課內作業(yè) 
		
            
	
            
	
	





            
	    
    


            

            Feedback
            
	
	
			
            
				# re: POJ 3604 Professor Ben
					
						2014-02-02 12:18
					
				kkkwjx
			
            
			
            
				N = P1^A1 + P2^A2 + . + Pk^Ak

            這里為什么是相加而不是相乘？  回復  更多評論
				  
				
			
            
		

            

            




            






            

				

            


    
    







            
	   
	



蜜桃麻豆www久久国产精品|
久久婷婷色香五月综合激情|
伊人丁香狠狠色综合久久|
国产AⅤ精品一区二区三区久久|
狠狠久久综合|
久久久免费精品re6|
久久综合九色欧美综合狠狠|
久久久av波多野一区二区|
色综合久久88色综合天天 |
精品久久人妻av中文字幕|
性高朝久久久久久久久久|
天天爽天天爽天天片a久久网|
久久婷婷色香五月综合激情|
精品熟女少妇aⅴ免费久久|
久久99精品国产自在现线小黄鸭|
国产农村妇女毛片精品久久|
国产成人综合久久综合|
奇米综合四色77777久久|
综合久久精品色|
精品久久国产一区二区三区香蕉|
丰满少妇高潮惨叫久久久|
性做久久久久久久|
亚洲女久久久噜噜噜熟女|
2021国内精品久久久久久影院|
久久中文字幕视频、最近更新|
国产精品gz久久久|
久久综合丁香激情久久|
国产精品福利一区二区久久|
亚洲va久久久噜噜噜久久|
2021久久精品免费观看|
国产精品久久久久蜜芽|
东方aⅴ免费观看久久av|
无码人妻少妇久久中文字幕蜜桃|
亚洲七七久久精品中文国产|
欧美精品福利视频一区二区三区久久久精品
|
老司机午夜网站国内精品久久久久久久久|
伊人久久大香线蕉综合影院首页
|
久久66热人妻偷产精品9|
久久精品水蜜桃av综合天堂|
色欲综合久久躁天天躁蜜桃|
久久精品黄AA片一区二区三区|