提出 #41076054

---

ソースコード 拡げる

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

template<class T> inline bool chmin(T& a, T b){ if (a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b){ if (a < b){a = b; return true;} return false;}

//using mint = modint998244353;
//using mint = modint1000000007;
//using mint = modint;  // mint::set_mod(p); later
//using mint = static_modint<1000000009>;

int main()
{
  cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

  ll N;
  int P;
  cin >> N >> P;

  vector<bool> sieve(101);
  vector<int> primes;

  // エラトステネスの篩
  for (int i = 2; i*i <= 100; i++){
    if (sieve[i]) continue;
    for (int j = 2; i*j <= 100; j++){
      sieve[i*j] = true;
    }
  }

  for (int i = 2; i < 100; i++){
    if (!sieve[i]) primes.push_back(i);
  }

  // Solve
  vector<ll> vec1, vec2;
  vec1.push_back(1);
  vec2.push_back(1);

  for (int x : primes){
    if (x > P) break;

    if (vec1.size() > vec2.size()){
      swap(vec1, vec2);
    }

    int sz = (int) vec1.size();
    
    for (int i = 0; i < sz; i++){
      ll v = vec1[i];
      v *= x;
      while (v <= N){
	vec1.push_back(v);
	v *= x;
      }
    }
  }

  ll ans = 0;
  sort(vec2.begin(), vec2.end());

  for (ll x : vec1){
    ll y = N / x;
    auto p = upper_bound(vec2.begin(), vec2.end(), y);
    int count = (int) (p - vec2.begin());
    ans += count;
  }

  cout << ans << endl;
  return 0;
}

提出情報

ジャッジ結果