• <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 、課內作業 
		
            
	
            
	
	





            
	    
    


            

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

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

            

            




            






            

				

            


    
    







            
	   
	



国产香蕉97碰碰久久人人|
亚洲人成无码www久久久|
久久久久无码精品国产|
久久777国产线看观看精品|
久久久久中文字幕|
国产精品久久久久久久人人看|
无码国内精品久久人妻|
99久久综合狠狠综合久久|
久久亚洲日韩精品一区二区三区|
久久99国产精品99久久|
久久久久波多野结衣高潮|
精品久久久久久无码人妻热
|
9999国产精品欧美久久久久久|
久久久WWW免费人成精品|
国内精品伊人久久久久AV影院|
免费精品久久久久久中文字幕|
国产91色综合久久免费分享|
久久久午夜精品|
日本亚洲色大成网站WWW久久|
一本色道久久88加勒比—综合|
久久久久久亚洲AV无码专区|
亚洲综合日韩久久成人AV|
狠狠色伊人久久精品综合网|
精品国产福利久久久|
成人妇女免费播放久久久|
无码人妻久久久一区二区三区|
蜜桃麻豆WWW久久囤产精品|
99久久成人18免费网站|
伊人久久大香线焦综合四虎|
久久精品成人免费看|
精品综合久久久久久888蜜芽|
久久男人Av资源网站无码软件|
人妻精品久久久久中文字幕一冢本|
久久久久久久久波多野高潮|
久久www免费人成看片|
囯产精品久久久久久久久蜜桃|
日韩精品无码久久久久久|
少妇高潮惨叫久久久久久|
99久久精品日本一区二区免费|
国内精品久久九九国产精品|
伊人久久大香线蕉影院95|