https://www.acmicpc.net/problem/1300
시간 2초, 메모리 128MB

input :

• 배열의 크기 N (1 ≤ N ≤ 100,000)
• k (min(10^9, N^2))

output :

• B[k]를 출력

조건 :

• 배열에 들어있는 수 A[i][j] = i×j

• 일차원 배열 B, 오름차순 정렬했을 때, B[k]

---

1 2 3
2 4 6
3 6 9

1 2 2 3 3 4 6 6 9


1 2 3 4
2 4 6 8
3 6 9 12
4 8 12 16

01 02 03 04 05
02 04 06 08 10
03 06 09 12 15
04 08 12 16 20
05 10 15 20 25

01 02 03 04 05 06
02 04 06 08 10 12
03 06 09 12 15 18
04 08 12 16 20 24
05 10 15 20 25 30
06 12 18 24 30 36

방법을 계속 몰랐다. 모든 숫자를 정렬해야 하나 하는 이상한 사고만 하고 있었다.

다음 풀이 때 생각할 방법

1. 특정 숫자를 지정한다면?
2. 해당하는 수보다 작은 놈들을 어떻게 셀 수 있을까?
3. 빠르게 탐색?

-> 1. 3. 에 대해서 이분 탐색을 사용하고
-> 2. 에 대해서 반복문을 돌며 해당하는 배열에서 자기 보다 작은 놈을 찾는다.

규칙으로는 구구단이라는 것이었다. 근데 이거 보다 나눗셈을 해서 몫을 체크 하면 해당하는 개수를 알 수 있다는 것이 유효하다.

import sys

n = int(sys.stdin.readline())
k = int(sys.stdin.readline())

low, high = 1, n * n
while low <= high:
    mid = (low + high) // 2
    cnt = 0

    for i in range(1, n + 1):
        if mid % i != 0:
            cnt += min(n, mid // i)
        else:
            cnt += min(n, mid // i - 1)

    if cnt + 1 > k:
        high = mid - 1
    else:
        low = mid + 1

print(high)