CFR 177 B2. Rectangular Game ( DP )

Problem - B2 - Codeforces
Having done so many ( not really many though ) problems, I always warn myself to think of an easier solution. Anyways, this could be solved with DP. Since MAXN = 1e9, and 2*3*7*11*13*17*19*31*37 ≥ 2e9, there will be at most 2^9 ≤ 1000 factors. Thus there are 1000 states of transitions, and each transition cost sqrt( N ) at most, the time complexity will be O( sqrt( N ) * 1000 ), which is totally safe.

int N;
map< int, int > dp;

void dfs( int x ){
    if( dp.count( x ) ) return;
    if( x == 1 ) return ( void )( dp[ 1 ] = 1 );
    for( int i = 2; i * i <= x; ++i ){
        if( x % i != 0 ) continue;
        dfs( x / i );
        dp[ x ] = max( dp[ x ], dp[ x / i ] + x );
    }
    dp[ x ] = max( dp[ x ], 1 + x );
}

void solve(){
    cin >> N;
    dfs( N );
    cout << dp[ N ] << "\n";
}