Submission #994222

---

Source Code Expand

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
typedef long long int lli;
vector<lli> seive(1e7, -1);
vector<bool> is_prime(1e7, true);

void func(lli n){
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i <= n; i++) {
    if(is_prime[i] == false)continue;
    seive[i] = i;
    for (int j = 2*i; j <= n; j+=i) {
      is_prime[j] = false;
      seive[j] = i;
    }
  }
}

vector<lli> fact(lli i){
  vector<lli> res;
  while(i > 1){
    res.emplace_back(seive[i]);
    i /= seive[i];
  }
  return res;
}
int main(){
  lli n, a;
  std::cin >> n >> a;
  func(n);
  vector<lli> cost(n + 1, 1e9);
  cost[0] = 0;
  cost[1] = 1;
  for (int i = 2; i <= n; i++) {
    vector<lli> f = fact(i);
    cost[i] = min(cost[i], (lli)i);
    for (int j = 2*i; j <= n; j+=i) {
      cost[j] = min(cost[j], cost[i] + j/i + a);
    }
  }
  lli ans = 1e9;
  for (int i = 1; i <= n; i++) {
    ans = min(ans, (lli)(ceil((double)(n)/i) + cost[i] + a));
  }
  std::cout << ans << std::endl;
  return 0;
}

Submission Info

Judge Result