[C++知识库]AcWing 3783. 第 k 个除数

问题描述

给定两个整数$n$和$k$，请你找到并输出能够整除$n$的第$k$小的正整数。

输入格式：

一行，两个整数$n$和$k$。

输出格式：

输出能够整除$n$的第$k$小的整数。

如果不存在，则输出$?1$。

数据范围

$1\le n\le 10^{15}$，
$1\le k\le 10^9$。

输入样例1：

4 2

输出样例1：

2

输入样例2：

5 3

输出样例2：

-1

思路

原题链接

C++代码：

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

int main()
{
    vector<LL> v;
    LL n, k;
    cin >> n >> k;

    for (int i = 1; i <= n / i ; i ++ )
    {
        if (n % i == 0)
        {
            v.push_back(i);
            if (i != n / i) 
                v.push_back(n / i);
        }
    }
    
    sort(v.begin(), v.end());
   
    if (k > v.size()) cout << "-1" << endl;
    else cout << v[k - 1] << endl;
    
    return 0;
}

Java代码：

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        int k = sc.nextInt();
        ArrayList<Long> v = new ArrayList<>();
        
        for (long i = 1; i * i<= n; i ++ ){
            if (n % i == 0){
                v.add(i);
                if (i != n / i) v.add(n / i);
            }
                
        }
        
        Collections.sort(v);
        
        if (k > v.size()) System.out.println("-1");
        else System.out.println(v.get(k - 1));
    }
}