CFR 385 C. Bear and Prime Numbers ( DP )

Problem - C - Codeforces
題意：
給一個序列，接著多筆詢問。對於每筆詢問 [ l, r ] 需要輸出該區間中每一個質數是序列中多少數的因數，其總和。
解法：
序列中的任意一個數的貢獻是，它的質因數個數。反過來說，任意一個質因數的貢獻是序列中它的倍數個數。利用質數篩法的精神，可以在 O( N lg lg N ) 完成。

int N;
vi X;

void init(){
    cin >> N;
    X = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> X[ i ];
}

vi cnt;
vl pans;
vi np;

void preprocess(){
    pans = vl( ( int ) 1e7 + 1 );
    cnt = vi( ( int ) 1e7 + 1 );
    for( int i = 0; i < N; ++i )
        ++cnt[ X[ i ] ];
    np = vi( ( int ) 1e7 + 1 );
    for( int i = 2; i < ( int ) 1e7; ++i )
        if( not np[ i ] )
            for( int j = i; j <= ( int ) 1e7; j += i )
                np[ j ] = 1,
                pans[ i ] += cnt[ j ];
    for( int i = 2; i <= ( int ) 1e7; ++i )
        pans[ i ] += pans[ i - 1 ];
}

void solve(){
    int M; cin >> M;
    for( int i = 0; i < M; ++i ){
        int ql, qr; cin >> ql >> qr;
        upmin( ql, ( int ) 1e7 );
        upmin( qr, ( int ) 1e7 );
        cout << pans[ qr ] - pans[ ql - 1 ] << endl;
    }
}