Submission #994200

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF (1e9+1)
//#define INF (1LL<<59)


int dp[1000000];
int A;

vector<ll> divisor(ll n){
    vector<ll> ret;
    for(int i=1;i<=sqrt(n);i++){
        if(n%i==0){
            ret.pb(i);
            if(i!=n/i)ret.pb(n/i);
        }
    }
    //  sort(all(ret));
    return ret;
}


int main(){
    int n;
    cin>>n>>A;
    if(n>1e6||A>1e6)return 0;

    rep(i,1000000)dp[i] = INF;
    dp[1]=0;
    
    for(int i=2;i<n;i++){
        vector<ll> y = divisor(i);
        rep(j,y.size()){
            if(y[j]==i)continue;
            dp[i] = min<int>(dp[i],dp[y[j]]+(A+(i/y[j])));
        }
    }

    int ans = INF;
    
    rep(i,1000000){
        if(i==0)continue;
        ans = min<int>(dp[i] + (n+i-1)/i,ans);
    }
    
    cout<<ans<<endl;
}

Submission Info

Judge Result