結果

問題 No.106 素数が嫌い！2
ユーザー Min_25Min_25
提出日時 2016-05-15 14:06:25
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 2,752 bytes
コンパイル時間 889 ms
コンパイル使用メモリ 80,788 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-15 21:49:37
合計ジャッジ時間 1,593 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 1 ms
5,376 KB
testcase_14 AC 1 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cassert>
#include <cmath>
#include <cstring>

#include <iostream>
#include <vector>
#include <array>
#include <functional>

#define _fetch(_1, _2, _3, _4, name, ...) name
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c))
#define rep(...) _fetch(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__)

using namespace std;

using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using f80 = long double;

pair<vector<u64>, vector<u64>> prime_counts(u64 n) {
  u64 v = sqrt(n);
  vector<u64> smalls(v + 1), larges(v + 1);
  rep(i, 1, v + 1) smalls[i] = i - 1, larges[i] = u64(n / i) - 1;
  rep(i, 2, v + 1) if (smalls[i] > smalls[i - 1]) {
    u64 c = smalls[i - 1];
    u64 q = u64(i) * i;
    rep(j, 1, min(v, n / q) + 1) {
      u64 d = j * i;
      larges[j] -= (d <= v ? larges[d] : smalls[n / d]) - c;
    }
    for (u64 j = v; j >= q; --j) smalls[j] -= smalls[j / i] - c;
  }
  return make_pair(smalls, larges);
}

vector<u64> big_omegas(u64 N) {
  u32 sqrt_N = sqrt(N);
  vector<u64> cnts(64 - __builtin_clzll(N));
  cnts[0] += 1;
  if (N > 1) {
    auto pi = prime_counts(N);
    auto& smalls = pi.first, &larges = pi.second;
    auto primes = vector<u32>();
    rep(i, 2, sqrt_N + 1) if (smalls[i] > smalls[i - 1]) primes.push_back(i);
    primes.push_back(sqrt_N + 1);
    function< void(u64, int, int) > rec = [&](u64 n, int i, int c) {
      cnts[c + 1] += (n > sqrt_N ? larges[N / n] : smalls[n]) - smalls[primes[i] - 1];
      rep(j, i, primes.size()) {
        u32 p = primes[j];
        if (u64(p) * p > n) break;
        rec(n / p, j, c + 1);
      }
    };
    rec(N, 0, 0);
  }
  return cnts;
}

vector<u64> omegas(u64 N) {
  u32 sqrt_N = sqrt(N);
  vector<u64> cnts(64 - __builtin_clzll(N));
  auto pi = prime_counts(N);
  auto& smalls = pi.first, &larges = pi.second;
  auto primes = vector<u32>();
  rep(i, 2, sqrt_N + 1) if (smalls[i] > smalls[i - 1]) primes.push_back(i);
  primes.push_back(sqrt_N + 1);
  function< void(u64, int, int, int) > rec = [&](u64 n, int i, int p, int c) {
    cnts[c + 1] += (n > sqrt_N ? larges[N / n] : smalls[n]) - smalls[p];
    cnts[c] += 1;
    rep(j, i, primes.size()) {
      int q = primes[j];
      if (u64(q) * q > n) break;
      rec(n / q, j, q, c + (p != q));
    }
  };
  rec(N, 0, 1, 0);
  return cnts;
}

void solve() {
  u64 N, K;
  while (~scanf("%llu %llu", &N, &K)) {
    auto cnts = omegas(N);
    u64 ans = 0;
    rep(i, K, cnts.size()) ans += cnts[i];
    printf("%llu\n", ans);
  }
}

int main() {
  clock_t beg = clock();
  solve();
  clock_t end = clock();
  fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC);
  return 0;
}
0