首页 > 代码库 > vector、set 练习 k-th divisor

vector、set 练习 k-th divisor

2024-10-08 00:33:02   216人阅读

k-th divisor

 

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.

Example

Input
4 2
Output
2
Input
5 3
Output
-1
Input
12 5
Output
6
代码实现：
 1 #include<cstdio>
 2 #include <set>
 3 #include<vector>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<cmath>
 7 using namespace std;
 8 int main()
 9 {
10     set<long long int>a;
11     long long int n,k;
12     long long int p1,pp;
13     scanf("%lld%lld",&n,&k);
14     pp=sqrt(n);
15     for(int i=1; i<=pp; i++)
16     {
17         p1=n%i;
18         if(p1==0)
19         {
20             a.insert(n/i);
21             a.insert(i);
22         }
23     }
24     vector<long long int>v;
25     insert_iterator<vector<long long int> > in_it(v, v.begin());
26     copy(a.begin(), a.end(), in_it);
27     //printf("%d\n",v.size());
28     if(k>v.size())
29         printf("-1\n");
30 
31     else
32     {
33         printf("%lld\n", v[k-1]);
34     }
35 
36     return 0;
37 }

 

 

vector、set 练习 k-th divisor


联系
我们