TOJ 6 因數個數1 ( Math )
Test Online Judge
這題各種限制很緊,差點以為這個解法行不通 ( 或許我的解法也不是正解 )。
想著應該是要用篩法先預處理,利用質因數分解後的指數做組合算出答案。但如果傻傻地做,就會MLE,所以只能用 short存答案。這樣不會爆是很顯然的,因為最多只會有8個不同的質因數,這時候會有2^8 = 256個因數,不會再更多。最後是跑了一半的記憶體,但執行時間是 900ms / 1000 ms,很懷疑這是不是喇賽解法。
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e7 + 7; short ans[ MAXN ]; bool not_prime[ MAXN ]; void preSolve(){ for( int i = 1; i <= ( int )1e7; ++i ) ans[ i ] = 1; for( int i = 2; i <= ( int )1e7; ++i ){ if( !not_prime[ i ] ){ for( int j = i; j <= ( int )1e7; j += i ){ not_prime[ j ] = 1; int t = j; int k; for( k = 0; t % i == 0; ++k ) t /= i; ans[ j ] *= k + 1; } } } } void solve( int n ){ cout << ans[ n ] << "\n"; } int main(){ preSolve(); int T; scanf("%d", &T); while( T-- ){ int n; scanf("%d", &n); solve( n ); } return 0; }