UVa 294 Divisors
這題的加速關鍵就在於質因數分解
例如 360 = 2^3 + 3^2 + 5
那麼360的因數個數就是(3+1)*(2+1)*(1+1)
其實作到質因數分解就可以在UVa拿到AC了
不過ZeroJudge的測資顯然要嚴酷許多
所以我建了質數表增加質因數分解的效率。
我解題時相當程度上參考了Sagit's code
http://www.tcgs.tc.edu.tw/~sagit/acm/view.php?id=294
簡潔易讀的寫法，相當佩服
這題我還有個心得就是gcc -O2 這個參數
對vector的速度影響非常大
我跑這個測資
有加-O2: 0.8 sec
加了O2後就極為逼近原生array的速度，幾乎看不出效能損失
只要有O2，我以後就可以開心的用vector啦 :D
例如 360 = 2^3 + 3^2 + 5
那麼360的因數個數就是(3+1)*(2+1)*(1+1)
其實作到質因數分解就可以在UVa拿到AC了
不過ZeroJudge的測資顯然要嚴酷許多
所以我建了質數表增加質因數分解的效率。
我解題時相當程度上參考了Sagit's code
http://www.tcgs.tc.edu.tw/~sagit/acm/view.php?id=294
簡潔易讀的寫法，相當佩服
這題我還有個心得就是gcc -O2 這個參數
對vector的速度影響非常大
我跑這個測資
1 999990000 1000000000不加-O2: 3.5 sec
有加-O2: 0.8 sec
加了O2後就極為逼近原生array的速度，幾乎看不出效能損失
只要有O2，我以後就可以開心的用vector啦 :D
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * UVa 294 Divisors | |
| * Author: chchwy | |
| * Last Modified: 2010.01.27 | |
| */ | |
| #include<cstdio> | |
| #include<cmath> | |
| #include<vector> | |
| using namespace std; | |
| enum {MAX = 1000000000, SQRT_MAX = 31622}; //sqrt(1000000000) = 31622 | |
| char isPrime[SQRT_MAX] = {0}; | |
| vector<int> primeNum; | |
| int shieve() | |
| { | |
| isPrime[0] = 0; | |
| isPrime[1] = 0; | |
| isPrime[2] = 1; | |
| for (int i = 3; i < SQRT_MAX; ++i) | |
| isPrime[i] = i % 2; | |
| //shieve | |
| int sqrt_n = sqrt((int)SQRT_MAX); | |
| for (int i = 3; i < sqrt_n; i += 2) | |
| { | |
| if (isPrime[i] == 0) continue; | |
| for (int j = i * i; j < SQRT_MAX; j += i) | |
| isPrime[j] = 0; | |
| } | |
| //push all prime number into vector "primeNum" | |
| for (int i = 2; i < SQRT_MAX; ++i) | |
| if (isPrime[i]) | |
| primeNum.push_back(i); | |
| } | |
| //回傳 num 總共有幾個divisor | |
| int getDivisorNumber(int n) | |
| { | |
| if ( n == 1 ) return 1; | |
| if ( n < SQRT_MAX && isPrime[n] ) return 2; | |
| int total = 1; | |
| int tmp = n; | |
| for (int i = 0 ; i < primeNum.size() && primeNum[i]*primeNum[i] <= n; ++i) | |
| { | |
| int div = primeNum[i]; | |
| int exp = 1; //算這個因數總共有幾個 | |
| for ( ; tmp % div == 0 ; exp++ ) | |
| { | |
| tmp /= div; | |
| } | |
| total *= exp; | |
| if ( tmp == 1 ) return total; | |
| } | |
| if (total != 1) return total * 2; //還剩下一個大於sqrt(n)的因數 | |
| return 2; | |
| } | |
| int main() | |
| { | |
| #ifndef ONLINE_JUDGE | |
| freopen("294.in", "r", stdin ); | |
| #endif | |
| shieve(); //build the prime table | |
| int numCase; | |
| scanf("%d", &numCase); | |
| while (numCase--) | |
| { | |
| int a, b; | |
| scanf("%d %d", &a, &b); | |
| int maxi = 0, maxDiv = 0; | |
| for ( int i = a; i <= b; ++i) | |
| { | |
| int curDiv = getDivisorNumber(i); | |
| if ( curDiv > maxDiv ) | |
| { | |
| maxi = i; | |
| maxDiv = curDiv; | |
| } | |
| } | |
| printf("Between %d and %d, %d has a maximum of %d divisors.\n", a, b, maxi, maxDiv); | |
| } | |
| return 0; | |
| } |
留言
張貼留言