2

每日一小题——试除法

 2 years ago
source link: https://blog.csdn.net/qq_52139998/article/details/120519754
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

每日一小题——试除法

芋头丝 2021-09-27 23:38:41 13

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

输入格式
一行，两个整数 n 和 k。

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

如果不存在，则输出 −1。

数据范围
1≤n≤1015，
1≤k≤109。
##代码模板

vector<int> get_divisors(int x)
{
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    sort(res.begin(), res.end());
    return res;
}

题解（数论）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k;
vector<ll> a;
int main()
{
    cin >> n >> k;
    for(ll i = 1; i * i <= n; i++)//试除法
    {
        if(n%i == 0)
        {
            a.push_back(i);//把能够整除n的数字放进a中
            if(i != n / i)
            a.push_back(n / i);//能够被i整除，那么n/i也能被整除
        }
        
    }
    sort(a.begin(),a.end());
    if(k > a.size()) cout << -1 << endl;
    else cout << a[k - 1] << endl;
    return 0;
}

###debug心得
在这里插入图片描述

因为数据很大，所以一定要开long long !
i要从1开始，否则n/i时会报错！
if语句的括号要考虑清楚才舍掉！


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK