CFR 558 C. Amr and Chemistry ( Ad hoc, Shortest Path )

Problem - C - Codeforces
First we should notice that if some number x does not include factor p ( p > 2 and p is not of form 2^k ), it can never be p nor a multiple of p. We should also realize it is impossible that the optimal answer is of making all values in to some number greater than the maximum value in the original array, because if that is so, the last round of multiplication for all numbers can be undone, making it more optimal. Therefore, it is feasible to search all possible values each value in the original array could reach, because going down to 1 needs traverse at most lg ( maxa ), and coming up back needs lg( maxa ) as well. Then we will go through each value, upon verifying that all the numbers in the original array can reach, update the cost.

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

    int max_a = *max_element( A.begin(), A.end() );
    vi vis( max_a + 1, -1 ), cnt( max_a + 1 ), step_sum( max_a + 1 );
    for( int i = 0; i < N; ++i ){
        queue< pii > que;
        que.push( pii( A[ i ], 0 ) );
        vis[ A[ i ] ] = i;
        while( not que.empty() ){
            int u = que.front().first;
            int w = que.front().second;
            que.pop();
            ++cnt[ u ];
            step_sum[ u ] += w;
            if( u * 2 <= max_a and vis[ u * 2 ] != i )
                vis[ u * 2 ] = i,
                que.push( pii( u * 2, w + 1 ) );
            if( vis[ u / 2 ] != i )
                vis[ u / 2 ] = i,
                que.push( pii( u / 2, w + 1 ) );
        }
    }

    int ans = 1e9;
    for( int i = 1; i <= max_a; ++i )
        if( cnt[ i ] == N )
            upmin( ans, step_sum[ i ] );

    cout << ans << endl;
}