Codefroces 762A k-th divisor 数论

题目大意:

给定两个正整数n,k\((n \le 10^{15},k\leq10^9)\)，求n的从小到大的第k个约数，无解输出-1

分析:

我们会自然而然地想到找出n的所有的约数，然后取第k个。

我们发现如果这样的话时间复杂度为\(O(\sqrt{n})\)，空间复杂度为\(O(lnn)\)

所以我们暴力上就好了

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

template<typename T>inline void read(T &x){

	x=0;char ch;bool flag = false;

	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

inline ll cat_max(const ll &a,const ll &b){return a>b ? a:b;}

inline ll cat_min(const ll &a,const ll &b){return a<b ? a:b;}

ll a[2000010],cnt1;

ll b[2000010],cnt2;

int main(){

	ll n,k;read(n);read(k);

	for(ll i=1;i*i<=n;++i){

		if(n % i == 0){

			a[++cnt1] = i;

			if(i*i != n) b[++cnt2] = n/i;

		}

	}

	if(k > cnt1 + cnt2) puts("-1");

	else{

		if(k <= cnt1){

			printf("%I64d\n",a[k]);

		}else{

			k -= cnt1;

			printf("%I64d\n",b[cnt2-k+1]);

		}

	}

	getchar();getchar();

	return 0;

}

巴特西

Codefroces 762A k-th divisor 数论

题目大意:

分析:

最新文章

热门文章