#P16837. [NWRRC 2021资格赛]N-有趣数

[NWRRC 2021资格赛]N-有趣数

题目描述

对于整数 X≥2X\ge 2,设它的质因数分解为

X=p1p2⋯pk,X=p_1p_2\cdots p_k,

其中质因数按重数计入,并设最大的质因数为 pmax⁡p_{\max}。

如果同时满足

pmax⁡ k≤Np_{\max}^{\,k}\le N

以及

pmax⁡≤127,p_{\max}\le 127,

那么称 XX 是一个 NN-有趣数。

给定两个整数 NN 和 nn。保证 NN-有趣数的总数是有限的,并且至少存在 nn 个。

请找出所有 NN-有趣数按从大到小排序后的第 nn 个。

输入格式

一行包含两个整数 N,nN,n:

2≤N≤1018,1≤n≤8⋅105.2\le N\le 10^{18},\qquad 1\le n\le 8\cdot 10^5.

输出格式

输出一个整数,表示按从大到小排序后的第 nn 个 NN-有趣数。

样例

3110 21
1573