0w1

CFR 703 E. Mishka and Divisors ( Math + DP )

Problem - E - Codeforces
It was quite disgusting, for many optimisations were required. I read pekempey's article and I think it is easy to understand.
pekempey.hatenablog.com
The small / large id reference especially made me learn something.
In the actual DP part, I originally wrote as what I have commented there, and received TLE. Since that loop is very large, it is important to keep everything down and reduce unnecessary recalculation.

typedef long long ll;
typedef pair< int, int > pii;
typedef pair< int, ll > pil;
typedef pair< ll, int > pli;
typedef pair< ll, ll > pll;
typedef vector< int > vi;
typedef vector< vi > vvi;

const int INF = 0x3f3f3f3f;

template< class T1, class T2 >
bool upmax( T1 &x, T2 v ){
    if( x < v ) return ( x = v ) or true;
    return false;
}

template< class T1, class T2 >
bool upmin( T1 &x, T2 v ){
    if( x > v ){
        x = v;
        return true;
    }
    return false;
}

vector< ll > get_divisors( ll k ){
    vector< ll > res;
    int sk = sqrt( k );
    for( int i = 1; i <= sk; ++i ) if( k % i == 0 ){
        res.push_back( i );
        if( k / i != i )
            res.push_back( k / i );
    }
    sort( res.begin(), res.end() );
    return res;
}

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

    if( K == 1 ){
        cout << 1 << "\n";
        cout << min_element( A.begin(), A.end() ) - A.begin() + 1 << "\n";
        return;
    }

    vector< ll > divisor = get_divisors( K );

    int sk = sqrt( K );
    vi small_divisor_id( sk + 1 );
    vi large_divisor_id( sk + 1 );
    for( int i = 0; i < divisor.size(); ++i ){
        if( divisor[ i ] <= sk )
            small_divisor_id[ divisor[ i ] ] = i;
        else
            large_divisor_id[ K / divisor[ i ] ] = i;
    }

    vector< vector< pil > > dp( N + 1, vector< pil >( divisor.size() ) );
    vector< vector< pii > > pre( N + 1, vector< pii >( divisor.size() ) );
    for( int i = 0; i <= N; ++i )
        for( int j = 0; j < divisor.size(); ++j )
            dp[ i ][ j ] = { N, 1e16 },
            pre[ i ][ j ] = { -1, -1 };

    dp[ 0 ][ 0 ] = { 0, 0 };
    for( int i = 0; i < N; ++i ){
        ll a = __gcd( A[ i ], K );
        for( int j = 0; j < divisor.size(); ++j ){
            if( dp[ i ][ j ] == pil( N, 1e16 ) ) continue;
            if( upmin( dp[ i + 1 ][ j ], dp[ i ][ j ] ) )
                pre[ i + 1 ][ j ] = { i, j };
            // ll nd = __gcd( divisor[ j ], K ) * __gcd( A[ i ], K / __gcd( divisor[ j ], K ) );
            ll nd = a * __gcd( divisor[ j ], K / a );
            int nj = nd <= sk ? small_divisor_id[ nd ] : large_divisor_id[ K / nd ];
            if( upmin( dp[ i + 1 ][ nj ], pil( dp[ i ][ j ].first + 1, dp[ i ][ j ].second + A[ i ] ) ) )
                pre[ i + 1 ][ nj ] = { i, j }; // , cout << i << " " << j << " -> " << nj << endl;
        }
    }

    if( dp[ N ][ divisor.size() - 1 ] == pil( N, 1e16 ) ){
        cout << -1 << "\n";
        return;
    }

    vi ans;
    for( int i = N, j = divisor.size() - 1; ; ){
        int ni = pre[ i ][ j ].first;
        int nj = pre[ i ][ j ].second;
        if( ni == -1 ) break;
        if( j != nj ) ans.push_back( ni + 1 );
        i = ni, j = nj;
    }

    cout << ans.size() << "\n";
    for( int i = 0; i < ans.size(); ++i )
        cout << ans[ i ] << ( i + 1 == ans.size() ? '\n' : ' ' );
}