1300 - K번째 수

 

1300번: K번째 수

 

#include <stdio.h>

typedef long long LL;

const LL MAX = 1e5 * 1e5;

LL N, M;
LL R;

LL min(LL x, LL y) { return x > y ? y : x; }

void init() {
  scanf("%lld", &N);
  scanf("%lld", &M);
}

LL cal(LL m) {
  LL count = 0;

  for (int n = 1; n <= N; ++n) {
    count += min(m, N * n) / n;
  }

  return count;
}

void bs(LL s, LL e) {
  if (s > e) {
    return;
  }

  LL m = (s + e) / 2;

  if (cal(m) >= M) {
    R = m;
    bs(s, m - 1);
  } else {
    bs(m + 1, e);
  }
}

int main(void) {
  // freopen("1300.txt", "r", stdin);
  
  init();

  bs(1, MAX);

  printf("%lld", R);

  return 0;
}

 

이분 탐색 + 수학 (구하려는 값보다 작은 수가 몇 개인지 어떻게 알 수 있을까 ?)

 

갯수 구할 때, 최소 구하기 어려웠당.