Submission #994822

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
#include<cassert>
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> prime_factorization(ll n){
    vector<ll> ret;
    
    for(ll div=2;div<=1+sqrt(n);div++){
        while(n%div==0){
            ret.pb(div);
            n/=div;
        }
    }
    if(n!=1)ret.pb(n);
    return ret;
}

int main(){
    int n;
    cin>>n>>A;
    assert(n<=1e6&&A<=1e6);

    rep(i,1000000)dp[i] = INF;
    dp[1]=0;
    
    for(int i=2;i<n;i++){
        vector<ll> pf = prime_factorization(i);
        int sum = 0;
        rep(j,pf.size())sum+=pf[j];
        dp[i] = sum+A*pf.size();
    }

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

//    
//    rep(i,200000){
//        if(i==0)continue;
//        if(dp[i] + (n+i-1)/i == ans){
//            cout<<i<<" "<<endl;
//        }
//    }

    
    
    cout<<ans<<endl;
}

Submission Info

Judge Result