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

Problem - B - Codeforces

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