백준 1557번: 제곱 ㄴㄴ

문제링크

https://www.acmicpc.net/problem/1557

1557번: 제곱 ㄴㄴ

풀이

1. $f(x)$: x 이하의 제곱 ㄴㄴ 수 개수
2. $f(t) = K$ 인 제일 작은 t 가 답이고 parametric search 로 찾는다.
3. $f(t)$ 구현
   1. $t - $ ($\sqrt{t}$ 이하의 소수들의 조합으로 구성된 수들의 제곱의 합집합 개수)
   2. 포함배제의 원리로 홀수종류 포함은 더하기, 짝수종류 포함은 빼기

 

코드

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  vector<long long> prime;
  vector<int> isPrime(sqrt(2e9) + 1, true);
  isPrime[0] = isPrime[1] = false;
  for (int i = 2; i * i < isPrime.size(); ++i) {
    if (!isPrime[i]) continue;
    for (int j = i * i; j < isPrime.size(); j += i) {
      isPrime[j] = false;
    }
  }
  for (int i = 2; i < isPrime.size(); ++i) {
    if (isPrime[i]) prime.push_back(i);
  }

  // 1 이상 x 이하 제곱 ㄴㄴ 수 개수
  auto getNum = [&](long long x) {
    // cnt, idx, num
    queue<tuple<int, int, long long> > q;
    for (int i = 0; i < prime.size(); ++i) {
      auto e = prime[i];
      if (e * e > x) break;
      q.push({1, i, e});
    }

    long long ret = 0;
    map<int, int> visited;
    while (q.size()) {
      auto [fcnt, fidx, fn] = q.front();
      q.pop();

      ret += (fcnt & 1 ? 1LL : -1LL) * (x / (fn * fn));

      for (int i = fidx + 1; i < prime.size(); ++i) {
        auto e = prime[i];
        if (fn * e * fn * e > x) break;
        if (fn % e == 0) continue;
        q.push({fcnt + 1, i, fn * e});
      }
    }
    return x - ret;
  };

  long long lo = 0;
  long long hi = 2e9;

  long long K;
  cin >> K;
  while (lo + 1 < hi) {
    long long mid = (lo + hi) >> 1;
    if (getNum(mid) < K) lo = mid;
    else hi = mid;
  }
  cout << hi << '\n';
}