D_2 - p×q

2 secs 1024 MB

step1: エストラテネスで $K$ までの素数を列挙します。 $K$ 以下の素数の個数を $σ(K)$ とします。

step2.「小さい方から $X$ 番目」を言い換えると、「ある数 $n$ 以下で $pq$ と表せる数がちょうど $X$ 個 ある」となります。
$f(n):=$ 整数 $n$ 以下で $pq$ と表せる数の個数とします。 $f(n)$ は単調増大であるので答えは $X≦f(n)$ となる最小の $n$ となり、二分探索で求めることができます。

step3. $f(n)$ を高速に求める方法を考えます。
$p$ を固定し、条件を満たす $q$ の数を求めます。以下の式で $f(n)$ を $log(σ(K))$ で求めることが出来ます。 $2$ 以上の整数について、素因数分解は一意に定まるので、 $p, q$ を入れ替えたケースを除いて、重複を考える必要はありません。すなわち $p≦q$ とすることで簡単に数え上げることが出来ます。
1 (小)
上図より、 $p$ を定めた時の $q$ の個数は、 $L[i]≦{\lfloor\frac{n}{L[i]}}\rfloor$ を満たす $i$ で、 $(紫色の長さ)=(赤色の長さ)+(青色の長さ)-(素数リストの長さ)$ 、それ以外で $(紫色の長さ)=0$ です。
二分探索を使い、以下の式で $f(n)$ を $log(σ(K))$ で求めることが出来ます。
足し合わせる $i$ の範囲は $L[i]≦{\lfloor\frac{n}{L[i]}}\rfloor$ を満たす $i$ とし、
$f(n) = \sum_{i} ge(L[i]) + le({\lfloor\frac{n}{L[i]}}\rfloor)) - l$
です。
$ge(x):= L$ のうち、 $x$ 以上の要素の個数
$le(x):= L$ のうち、 $x$ 以下の要素の個数

$K$ 以下の最大の素数を $K_m$ とすると、計算量は $O(log(K_m)^2σ(K)logσ(K))$ です。

Python

from bisect import *

def prime_L(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def idx_le(A, x): # x 以下の最大の要素位置 / なければ "No"
    return bisect_right(A, x)-1 if bisect_right(A, x)-1 != -1 else "No"

def idx_lt(A, x):  # x 未満の最大の要素位置 / なければ "No"
    return bisect_left(A, x)-1 if bisect_right(A, x)-1 != -1 else "No"

def idx_ge(A, x): # x 以上の最小の要素位置 / なければ "No"
    return bisect_left(A, x) if bisect_left(A, x) != len(A) else "No"

def idx_gt(A, x): # x 超過の最小の要素位置 / なければ "No"
    return bisect_right(A, x) if bisect_right(A, x) != len(A) else "No"

def cnt_le(A, x): # x 以下の要素の個数
    if(idx_le(A, x) == "No"): return 0
    return idx_le(A, x) + 1

def cnt_lt(A, x): # x 未満の要素の個数
    if(idx_lt(A, x) == "No"): return 0
    return idx_lt(A, x) + 1

def cnt_ge(A, x): # x 以上の要素の個数
    return len(A) - cnt_lt(A, x)
    
def cnt_gt(A, x): # x 超過の要素の個数
    return len(A) - cnt_le(A, x)

INF = 10**12

def f(n):
    cnt = 0
    for i in range(l):
        if(L[i] > n//L[i]): break
        cnt += cnt_ge(L,L[i])+cnt_le(L,n//L[i])-l
    return cnt

k,x = map(int,input().split())
L = prime_L(k)
l = len(L)
ng = -1
ok = INF
while abs(ok-ng)>1:
    mid = (ok+ng)//2
    if(f(mid)>=x):
        ok = mid
    else:
        ng = mid

print(ok)

別解

二分探索と尺取り法を用いた解法

C++

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
	ll k, x;
	cin >> k >> x;

	vector<ll> primes;
	vector<ll> lpf(k + 1, 0);
	for(ll i = 2; i <= k; i++){
		if(lpf[i] == 0){
			lpf[i] = i;
			primes.push_back(i);
		}
		for(auto p: primes){
			if(p * i > k || p > lpf[i]) break;
			lpf[p * i] = p;
		}
	}
	ll n = primes.size();

	auto f = [&](ll mid) -> ll {
		ll res = 0;
		int ok = n - 1;
		for(int i = 0; i < n; i++){
			while(ok >= 0 && primes[ok] * primes[i] > mid) ok--;
			res += min(i + 1, ok + 1);
		}
		return res;
	};

	ll ng = 1, ok = k * k;
	while(ok - ng > 1){
		ll mid = (ok + ng) / 2;
		if(f(mid) < x) ng = mid;
		else ok = mid;
	}
	
	cout << ok << endl;
}