NN단표

문제

알랩이는 구구단표처럼 NN단표를 만들었다고 한다.

NN단표는 2차원 배열의 모양으로 곱셈 1단부터 N단까지의 값들을 적어놓은 형태이다.

NN단표의 배열을 A라고 했을 때, 배열의 들어가는 수 A[i][j]=i*j이다.(즉, 4행 7열에는 28, 7행 5열에는 35가 들어가 있다.)

알랩이는 N단까지 나온 숫자들 중에서 K번째로 작은 수를 찾고 싶어한다.

이때, 중복되는 여러 수들을 고려한다. 즉 N*N개의 모든 수들 중에서 K번째 수를 구하는 것이다.  

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄에 K가 주어진다. K는 N*N보다 작거나 같은 자연수이다.  

출력

K번째 원소를 출력한다.

 

예제 입력

3

7

예제 출력

6

 

// 코드

import java.util.*;
import java.io.*;
 
public class Main{
  
  static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  static long N, K;
  
  // k가 몇 번째인지 반환하는 함수.
  static long getOrder(long x) {
    
    long result = 0; 
    for(int i=1; i<=N; i++) {
      if((long)i*N < x) result += N;
      else {
        if(x%i == 0) result += (x/i)-1;
        else result += (x/i);  
      }
    } 
    return result + 1;
  }
  
  public static void main(String[] args) throws Exception {
 
    // Please Enter Your Code Here
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    K = Integer.parseInt(br.readLine());
    
    // 1 ~ n*n중 숫자 p가 몇 번째인가?
    long start = 1, end = (N*N) + 1;
    // start : 항상 정답이 되는 숫자보다 작거나 같은 숫자.
    // end : 항상 정답이 되는 숫자보다 큰 수자.
    while(start+1 < end) {
      long mid = (start + end) / 2;
      long myOrder = getOrder(mid); // mid라는 숫자가 몇 번째 숫자인지 알 수 있다.
      
      if(myOrder <= K) start = mid; // = 가 들어가야 없는 숫자가 아닌 반드시 있는 숫자만 찾아낸다.
      else end = mid;
    } 
    
    bw.write(String.valueOf(start));
    
    br.close();
    bw.flush();
    bw.close();
 
  }
}