• <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 閱讀(1736) 評論(1)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、Mathematics 、課內作業 
		
            
	
            
	
	





            
	    
    


            

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

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

            

            




            






            

				

            


    
    







            
	   
	



久久w5ww成w人免费|
久久久一本精品99久久精品88|
无码国内精品久久人妻|
久久亚洲国产成人精品性色|
成人精品一区二区久久|
免费精品国产日韩热久久|
精品永久久福利一区二区|
精品水蜜桃久久久久久久|
色欲综合久久躁天天躁蜜桃|
香蕉久久一区二区不卡无毒影院|
午夜精品久久久内射近拍高清
|
久久久久久久97|
无码精品久久久天天影视|
91精品国产高清91久久久久久|
很黄很污的网站久久mimi色|
久久影院综合精品|
伊人久久大香线蕉综合网站|
99久久国产亚洲高清观看2024|
无码人妻精品一区二区三区久久久
|
精品久久久久久国产三级|
久久久久国产精品嫩草影院|
久久青青草原综合伊人|
奇米影视7777久久精品|
精品久久人人爽天天玩人人妻|
国产激情久久久久影院老熟女|
久久天天躁狠狠躁夜夜躁2O2O|
久久久无码精品亚洲日韩京东传媒
|
精品久久久久久久国产潘金莲|
精品亚洲综合久久中文字幕|
亚洲午夜无码久久久久|
麻豆精品久久久久久久99蜜桃
|
国产91久久综合|
久久综合欧美成人|
aaa级精品久久久国产片|
国内精品久久久久影院优|
久久国产热精品波多野结衣AV|
伊人久久久AV老熟妇色|
亚洲综合伊人久久综合|
欧美喷潮久久久XXXXx|
久久天堂AV综合合色蜜桃网
|
日本精品久久久久影院日本|