Submission #7894955

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const int SIZE=1e6+1;
const ll INF=1e14;
const double eps=1e-9;

void cmin(ll &lhs,ll rhs){ lhs=min(lhs,rhs);}
int main(){
    ll n,a;
    cin>>n>>a;
    vector<ll> dp(SIZE,INF);
    dp[1]=0;
    for(int i=1;i<SIZE;i++){
        for(int j=2;i*j<SIZE;j++){
            ll t=dp[i]+j+a;
            cmin(dp[j*i],t);
        }
    }
    for(int i=SIZE-2;i>=0;i--) cmin(dp[i],dp[i+1]);
    if(n<SIZE) cout<<dp[n]-a<<endl;
    else{
        ll res=n;
        for(int i=1;i<20;i++){
            ll z=ceil(pow(n,1.0/i)-eps);
            for(int j=0;j<=i;j++){
                ll c=0;
                ll x=1;
                for(int k=0;k<j;k++){
                    c+=z+a;
                    x*=z;
                }
                for(int k=j;k<i;k++){
                    c+=(z-1)+a;
                    x*=(z-1);
                }
                c-=a;
                if(x>=n){
                    res=min(res,c);
                }
            }
        }
        cout<<res<<endl;        
    }
    return 0;
}

Submission Info

Judge Result