首页 > 代码库 > 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(数论+贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。