Submission #994166

---

Source Code Expand

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <limits>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int,int>
#define x first
#define y second
#define sf scanf
#define pf printf
#define vec vector
#define pb push_back
#define mp make_pair
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define clr(a,b) memset(a,b,sizeof(a))
#define bin_cnt(x) __builtin_popcount(x)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define srep(sub,s) for(int sub=s&(s-1);sub;sub=(sub-1)&s)
#define irep(i,a) for(__typeof(a.begin()) i=a.begin();i!=a.end();i++)
#define irrep(i,a) for(__typeof(a.rbegin()) i=a.rbegin();i!=a.rend();i++)
#define inf numeric_limits<int>::max()
#define finf numeric_limits<double>::infinity()
#define eps 1e-8
#pragma GCC optimize ("O3")
#define o3 __attribute__((optimize("O3")))
#pragma comment(linker, "/STACK:32505856")

template<class T> inline T sqr(T a) {return a*a;}
template<class T> inline int gmin(T&a,T b) {if(a>b){a=b;return 1;}return 0;}
template<class T> inline int gmax(T&a,T b) {if(a<b){a=b;return 1;}return 0;}
inline int dcmp(const double &a) {return a>eps?1:(a<-eps?-1:0);}
struct Initializer{Initializer(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}}initializer;

#define N 1000100
#define MAXN 1000010
vec<int> p;
vec<int> factors;
int np[MAXN] = {1, 1};

void get_primes() {
    for (int i = 2; i < MAXN; i++)
        if (!np[i]) {
            p.pb(i);
            for (int j = i + i; j < MAXN; j += i) {
                np[j] = 1;
            }
        }
}

void decompose(int n) {
    factors.clear();
    rep(i,0,sz(p) - 1) {
        while (n % p[i] == 0) {
            factors.pb(p[i]);
            n /= p[i];
            if (n == 1) return;
        }
    }
}


#define maxll 0x7fffffffffffffffll
ll n, ta;
ll f[N];
ll ans = maxll;

int main() {
//    get_primes();
    cin >> n >> ta;
    rep(i,2,n) f[i] = maxll;
    rep(i,1,n) {
        ll k = 2;
        for (ll j = i + i; j <= n; j += i, k ++) {
            ll tmp = f[i] + ta + k;
            if (f[j] > tmp) f[j] = tmp;
        }

        ll t = n / i;
        if (n % i) t++;
        t += f[i];
        if (ans > t) ans = t;
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result