k個の数字(1300)

Binary Search

質問する

勢俊の大きさはN×N人配列Aをしました.配列内の数A[i][j]=i×jです.この数を主アレイBに入れると、Bの大きさはNとなる.×Nになる.Bを昇順に並べてみるとB[k]を求めてみる.
配列AとBのインデックスは1から始まる.

入力

最初の行は配列のサイズNを与える.Nは105以下の自然数である.2行目はkを与える.kはmin(109,N 2)の自然数以下である.

しゅつりょく

B[k]を出力します.

import sys

input = sys.stdin.readline

n = int(input())
target = int(input())

low = 0
high = target
answer = 0

while low <= high:
    m = (low + high) // 2
    count = 0
    for i in range(1, n + 1):
        count = count + min(m // i, n)
        
    if count < target:
        low = m + 1
    else:
        answer = m
        high = m - 1
        
print(answer)

参照)
https://developmentdiary.tistory.com/354