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

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

            

            




            






            

				

            


    
    







            
	   
	



狠狠色丁香久久婷婷综合_中
|
久久精品成人免费国产片小草|
国产成人无码久久久精品一|
99久久久国产精品免费无卡顿|
99久久人妻无码精品系列|
99热热久久这里只有精品68|
久久夜色精品国产亚洲|
久久精品国产99国产精品导航|
99久久免费国产特黄|
一本色道久久88综合日韩精品
|
国产无套内射久久久国产|
亚洲精品NV久久久久久久久久
|
亚洲综合久久久|
久久久久久a亚洲欧洲aⅴ|
久久综合狠狠综合久久97色|
亚洲伊人久久大香线蕉苏妲己|
亚洲精品无码久久一线|
国产一区二区三精品久久久无广告
|
久久精品这里热有精品|
国产69精品久久久久APP下载|
久久亚洲国产成人精品性色|
伊人久久五月天|
日韩精品国产自在久久现线拍
|
精品久久久久久久|
久久久久久亚洲AV无码专区|
久久精品中文字幕一区|
99久久精品国产一区二区|
99国产欧美精品久久久蜜芽|
97久久国产露脸精品国产|
香蕉久久夜色精品国产尤物|
777久久精品一区二区三区无码|
久久国产精品99国产精|
亚洲综合熟女久久久30p|
波多野结衣久久一区二区
|
欧美一区二区三区久久综|
亚洲欧洲久久久精品|
中文精品久久久久人妻|
亚洲日本久久久午夜精品|
人妻系列无码专区久久五月天|
久久久久婷婷|
天天做夜夜做久久做狠狠|