Codeforces Educational Codeforces Round 17 Problem.A kth-divisor (暴力+stl)

You are given two integers n and k. Find k-th smallest divisor of n, or report that it doesn't exist.

Divisor of n is any such natural number, that n can be divided by it without remainder.

Input

The first line contains two integers n and k (1 ≤ n ≤ 1015, 1 ≤ k ≤ 109).

Output

If n has less than k divisors, output -1.

Otherwise, output the k-th smallest divisor of n.

Examples

input

4 2

output

input

5 3

output

-1

input

12 5

output

Note

In the first example, number 4 has three divisors: 1, 2 and 4. The second one is 2.

In the second example, number 5 has only two divisors: 1 and 5. The third divisor doesn't exist, so the answer is -1.

solution

原本想了个分解质因数后递推，但发现空间不够

其实可以用时间换空间，暴力嘛

随便做一做就行了

#include <math.h>

#include <vector>

#include <stdio.h>

#define L long long

char B[],*p=B,pb[];

inline void Rin(register L &x){

    x=;

    while(*p<''||*p>'')p++;

    while(*p>=''&&*p<='')

        x=x*10LL+*p++-'';

}

inline void Mo(register L x){

    register int top=;

    while(x)pb[++top]=(x%10LL)+'',x/=10LL;

    while(top)putchar(pb[top--]);

    putchar('\n');

}

L n,K,s,l1,l2;

std::vector<L>p1,p2;

int main(){

    fread(B,,,stdin);

    Rin(n),Rin(K);

    L s=sqrt(n);

    for(register L i=;i<s;i++)

        if(n%i==0LL){

            p1.push_back(i);

            p2.push_back(n/i);

        }

    if(s*s==n)

        p1.push_back(s);

    else

        if(n%s==){

            p1.push_back(s);

            p2.push_back(n/s);

        }

    l1=p1.size(),l2=p2.size();

    if(l1+l2<K)

        puts("-1");

    else{

        if(K<=l1)

            Mo(p1[K-]);

        else

            Mo(p2[l2-K+l1]);

    }

    return ;

}

巴特西

Codeforces Educational Codeforces Round 17 Problem.A kth-divisor (暴力+stl)

最新文章

热门文章