首页 > 代码库 > UVA 1521 - GCD Guessing Game(数论+贪心)

UVA 1521 - GCD Guessing Game(数论+贪心)

UVA 1521 - GCD Guessing Game

题目链接

题意:一个数字x在1-n之间,现在猜数字,每次猜一个数字a,告知gcd(x, a)的答案,问最坏情况下需要猜几次

思路:在素数上考虑,猜一组素数的乘积的数字,就可以把这些素数组成的数字都猜出来,答案就是组数,这样问题就是如何分组使得组数最小,每次取最后一个,尽量和前面小的合并,就能使得组数最小

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 10005;

int vis[N], prime[N], pn = 0;

void getprime() {
	for (int i = 2; i < N; i++) {
		if (vis[i]) continue;
		prime[pn++] = i;
		for (int j = i * i; j < N; j += i)
			vis[j] = 1;
	}
}

int n;

int main() {
	getprime();
	while (~scanf("%d", &n)) {
		int ans = 0, head = 0, rear = pn - 1;
		while (prime[rear] > n) rear--;
		while (head <= rear) {
			int p = prime[rear];
			while (p * prime[head] <= n) p *= prime[head++];
			ans++;
			rear--;
		}
		printf("%d\n", ans);
	}
	return 0;
}


UVA 1521 - GCD Guessing Game(数论+贪心)