首页 > 代码库 > uva 1521 - GCD Guessing Game(贪心)
uva 1521 - GCD Guessing Game(贪心)
题目链接:uva 1521 - GCD Guessing Game
题目大意:给定一个数N,现在又一个数x,在1~N之间,现在每次可以猜一个数a,返回gcd(x,a),问说最少猜几次可以确定x。
解题思路:其实就将1~N里面的素数都要考虑一遍,因为有一个N的限制,所以每次选出来的素数的积不大于N即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 10000;
int N, v[maxn];
int npri, vis[maxn+5], prime[maxn+5];
void prime_table (int n) {
npri = 0;
for (int i = 2; i <= n; i++) {
if (vis[i])
continue;
prime[npri++] = i;
for (int j = i * i; j <= n; j += i)
vis[j] = 1;
}
}
void set (int u, int x) {
for (int i = x; i >= 0; i--) {
int k = prime[i];
if (v[k] || k > u)
continue;
v[k] = 1;
set(u/k, i-1);
return;
}
}
int solve () {
int ans = 0;
memset(v, 0, sizeof(v));
for (int i = npri-1; i >= 0; i--) {
int u = prime[i];
if (v[u] || u > N)
continue;
ans++;
v[u] = 1;
set(N/u, i-1);
}
return ans;
}
int main () {
prime_table(maxn);
while (scanf("%d", &N) == 1) {
printf("%d\n", solve());
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。