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' : ' ' ); }