Submission #1023396

---

Source Code Expand

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
 
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define fin "\n"
 
 
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
 
template <typename T>
inline void chmin(T &l,T r){l=min(l,r);}
 
template <typename T>
inline void chmax(T &l,T r){l=max(l,r);}
LL A;
map<LL,LL> dp;

const int M=1e6;
LL val[M];
void init(){
    iota(val,val+M,0);
    FOR(i,1,M){
        for(int j=i+i,t=2;j<M;j+=i,t++)
            chmin(val[j],val[i]+A+t);
    }
    for(int i=M-2;i>=1;i--){
        chmin(val[i],val[i+1]);
    }

}
LL f(const LL n){
    if(dp.count(n))return dp[n];
    if(n<M)return val[n];
    //cout<<n<<endl;
    LL x=n,nx;
    LL y=n,ny;
    LL w=n;
    auto g=[&](LL i){
        if(i>n)return n;
        if(i<=1)return n;
        LL m=(n+i-1)/i;
        if(m==n)return n;
        return f(m)+A+i;
    };
    while(w>1){
        //cout<<n<<":"<<x<<" "<<y<<" "<<w<<endl;
        if ((ny=g(nx=x+w)) < y) y = ny, x = nx; 
        else if ((ny=g(nx=x-w)) < y) y = ny, x = nx;
        w=(w+1)/2;
    }
    LL ans=y;
    for(int i=-3;i<=3;i++)chmin(ans,g(x+i));
    //cout<<n<<" "<<ans<<endl;
    return dp[n]=min(ans,n);
}
int main(){
    
    LL N;
    dp[1]=1;
    cin>>N>>A;
    if(N==M)return -1;
    init();
    cout<<f(N)<<endl;
    return 0;
}

Submission Info

Judge Result