Eva

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 631  Solved: 345
Description

若一个大于1的整数M的质因数分解有k项，其最大的质因子为Ak，并且满足Ak^K<=N,Ak<128，我们就称整数M为N-伪

光滑数。现在给出N，求所有整数中，第K大的N-伪光滑数。

Input

只有一行，为用空格隔开的整数N和K

2 ≤ N ≤ 10^18， 1 ≤ K ≤ 800000，保证至少有 K 个满足要求的数

Output 

只有一行，为一个整数，表示答案。

Sample Input

12345 20

Sample Output

9167

HINT 

/**************************************************************

    Problem: 4524

    User: mywaythere

    Language: C++

    Result: Accepted

    Time:4356 ms

    Memory:124176 kb

****************************************************************/

 

#include <iostream>

#include <cstdio>

#include <queue>

using namespace std;

int pri[50]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127},cnt=31;

typedef long long ll;

struct data

{

    ll num;

    int maxpri_pos,nxtpri_pos;

    int maxpri_cnt;

};

priority_queue<data>q;

bool operator < (data a,data b)

{

    return a.num<b.num;

}

inline ll readll()

{

    ll num=0,flag=1;

    char ch;

    do{

       ch=getchar();

       if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

       num=num*10+ch-'0';

       ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

int main()

{

    ll n=readll(),k=readll();

    //for(int i=0;i<=cnt;i++)

        //cout<<pri[i]<<endl;

    for(int i=1;i<=cnt;i++)

    {

        ll x=1;

        for(int j=1;;j++)

        {

            x=x*1ll*pri[i];

            if(x>n) break;

            data now;

            now.num=x,now.maxpri_pos=i,now.nxtpri_pos=i-1,now.maxpri_cnt=j;

            q.push(now);

        }

    }

    data now;now.num=1;

    while(k--)

    {

        now=q.top();

        q.pop();

        if(now.maxpri_cnt>1)

        for(int i=now.nxtpri_pos;i>=1;i--)

        {

            data tmp=now;

            tmp.num=1ll*tmp.num/pri[now.maxpri_pos]*pri[i],tmp.maxpri_cnt-=1,tmp.nxtpri_pos=i;

            q.push(tmp);

        }

    }

    printf("%lld\n",now.num);

    return 0;

}