CFR 453 B. Little Pony and Harmony Chest ( bits DP + Math )

Problem - B - Codeforces
題意：
給一個序列 A，要你求一個相同長度的 B 序列，使 B 序列中任意兩個數字皆互質，此前提下 SIGMA{ abs( A[ i ] - B[ i ] ) } 最小。輸出 B 的長相。
解法：
A 最大只會有 30，可以證明 B 只需考慮 [ 1, 60 ] 內的數。因為如果某個 A[ i ] 對應的 B[ i ] > 2 * A[ i ]，讓 B[ i ] = 1 一定不會比較虧。因此可以考慮位元動態規劃。預處理質數表和須考慮的範圍內的數的質因數，用位元處理加速就可以降低複雜度。
dp[ i ][ j ] : 已考慮前 i 個數，此時已有的質數集合為 j ( 質數表中編號 )

int N;
vi A;

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

vi pt; // prime table
vi pv; // primes of values, in id of pt, compressed in bits

vvi dp;
vvi ds; // decision

void preprocess(){
    for( int i = 2; pt.size() < 17; ++i ){
        int np = 0;
        for( int j = 2; j * j <= i; ++j )
            if( i % j == 0 )
                np = 1;
        if( not np )
            pt.push_back( i );
    }
    pv = vi( 60 + 1 );
    for( int i = 2; i < pv.size(); ++i )
        for( int j = 0; j < pt.size(); ++j )
            if( i % pt[ j ] == 0 )
                pv[ i ] |= 1 << j;
    dp = ds = vvi( N + 1, vi( 1 << ( int ) pt.size(), INF ) );
    dp[ 0 ][ 0 ] = 0;
    for( int i = 0; i < N; ++i )
        for( int j = 0; j < 1 << ( int ) pt.size(); ++j )
            if( dp[ i ][ j ] < INF ){
                for( int k = 1; k < 2 * A[ i ]; ++k ){
                    int nj = j | pv[ k ], ng = pv[ k ] & j;
                    if( ng ) continue;
                    if( upmin( dp[ i + 1 ][ nj ], dp[ i ][ j ] + abs( A[ i ] - k ) ) )
                        ds[ i + 1 ][ nj ] = k;
                }
            }
}

void solve(){
    int minC = INF, minS = -1;
    for( int i = 0; i < 1 << ( int ) pt.size(); ++i )
        if( upmin( minC, dp[ N ][ i ] ) )
            minS = i;
    stack< int > ans;
    for( int i = N, j = minS; 0 < i; j ^= pv[ ds[ i-- ][ j ] ] )
        ans.push( ds[ i ][ j ] );
    for( ; not ans.empty(); ans.pop() )
        cout << ans.top() << " \n"[ ( int ) ans.size() == 1 ];
}