0w1

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;
}