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

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

            

            




            






            

				

            


    
    







            
	   
	



色欲久久久天天天综合网精品|
一级做a爱片久久毛片|
精品熟女少妇AV免费久久|
亚洲va久久久噜噜噜久久天堂|
久久精品aⅴ无码中文字字幕重口
久久精品a亚洲国产v高清不卡
|
欧洲成人午夜精品无码区久久|
欧美黑人激情性久久|
日韩精品国产自在久久现线拍
|
久久久亚洲欧洲日产国码二区|
国产精品VIDEOSSEX久久发布|
老男人久久青草av高清|
91精品国产91久久久久久|
久久久久久免费视频|
99精品伊人久久久大香线蕉|
久久精品国产乱子伦|
色99久久久久高潮综合影院|
精品久久久久久久无码
|
国产99久久九九精品无码|
久久久亚洲欧洲日产国码是AV|
国产精品伊人久久伊人电影|
久久亚洲私人国产精品vA|
日本五月天婷久久网站|
欧美性猛交xxxx免费看久久久|
成人国内精品久久久久一区|
久久久这里只有精品加勒比|
久久久国产一区二区三区|
一级做a爱片久久毛片|
精品午夜久久福利大片|
久久精品国产亚洲AV电影|
少妇精品久久久一区二区三区|
久久国产AVJUST麻豆|
欧美激情精品久久久久久久九九九
|
热re99久久精品国产99热|
久久超碰97人人做人人爱|
亚洲国产精品18久久久久久|
久久国产免费直播|
亚洲中文字幕无码久久精品1|
亚洲欧美成人综合久久久
|
久久久久高潮毛片免费全部播放|
中文字幕无码精品亚洲资源网久久|
久久久久av无码免费网|