icontofig | 发布于 2017-01-31 21:35:39 | 阅读量 297 | 模拟 数学
发布于 2017-01-31 21:35:39 | 模拟 数学

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.

题目大意:给出两个数n和k,求n的第k个因数,数据范围都看得懂……特别的,如果n没有第k个因数,就输出-1

不得不说CF的题目坑爹啊,非得用I64d或者流输入输出。。

这道题如果直接暴力枚举的话,会TLE的。。

所以根据某数学结论,我们可以在sqrt(n)内枚举n的因数,然后对应到后面的因数去。。。

然后两边都用vector存好了,因为vector是动态分配空间,不至于MLE,然后就在前sqrt(n)内暴力瞎搞就行了。。(我觉得还可以写内存池,不过太麻烦了)

这是一道好题。。

#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;
}​

 


内容更新于: 2017-01-31 21:35:48
链接地址: http://blog.leanote.com/post/icontofig/codeforces-762A-%E6%A8%A1%E6%8B%9F%E2%80%A6%E2%80%A6

上一篇: SDOI2013费用流

下一篇: 博弈论学习笔记

297 人读过
立即登录, 发表评论.
没有帐号? 立即注册
1 条评论
文档导航