codeforces 762A 模拟……

# A. 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 ≤ 10151 ≤ 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
`2`
input
`5 3`
output
`-1`
input
`12 5`
output
`6`
Note

In the first example, number 4 has three divisors: 12 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.

```#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
long long n,k;
int tot = 0;
int l1,l2;
vector<long long>v,vv;
int main(){
scanf("%I64d%I64d",&n,&k);
long long x = sqrt((double)n);
for(ll i = 1;i <= x;++i){
if(n % i == 0 && i * i != n){
tot += 2;
l1++;l2++;
v.push_back(i);
ll t = n / i;
vv.push_back(t);
}
else if(i * i == n){
tot++;l1++;
v.push_back(i);
}
}
if(k <= l1)
printf("%I64d\n",v[k-1]);
else if(k <= tot && k > l1)printf("%I64d\n",vv[l2-1-(k-l1)+1]);
else printf("-1\n");
return 0;
}﻿​```

1 条评论