k번째 수

Problem link: https://www.acmicpc.net/problem/1300

[1 ~ N * N] 범위의 자연수가 있다고 할 때 주어진 행렬에서 나보다 작거나 같은 수의 갯수가 K개인 수를 찾는 문제로 접근해준다.

찾아진 수가 행렬에 존재하지 않는 수일 수 있으므로 탐색은 lower_bound로 진행해준다.

행렬에 존재하는 수를 기준으로 나보다 작거나 같은 수의 갯수가 적어도 1개는 차이가 나게될 것이므로(본인도 세어주어야 하니까), 이 방법은 정당하다.

어떤 수보다 작거나 같은 행렬 내 수의 갯수를 세는 방법은 각 행을 1의 배수, 2의 배수, ...와 같이 생각해주면 쉽다.

#include <iostream>
#include <cstdint>
#include <algorithm>

using namespace std;

int64_t Solve(const int64_t n, const int64_t k, int64_t begin, int64_t end)
{
  // Find lower_bound
  while (begin < end)
  {
    int64_t mid = (begin + end) / 2;

    int64_t lesser = 0;
    for (int64_t div = 1; div <= n; ++div)
    {
      lesser += min(mid, div * n) / div;
    }

    if (lesser < k)
    {
      begin = mid + 1;
    }
    else
    {
      end = mid;
    }
  }

  return end;
}

int main(void)
{
  int64_t n, k;
  cin >> n >> k;
  cout << Solve(n, k, 1, n * n) << '\n';
}