2632: [neerc2011]Gcd guessing game
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 144 Solved: 84
[Submit][Status][Discuss]
Description
给定一个数n ,有一个数x , ( 1<=x<=n ) 每次你可以猜在[1,n]中的数,假设是y，如果x==y，游戏结束，如果没猜中，则告诉你gcd(x,y)，然后继续猜，直到猜中为止。
现在问给定n的情况下，最坏情况下最少要多少次猜中
Input
N
Output
最坏情况下最少猜中次数
Sample Input
6
Sample Output
2
HINT
2 ≤ n ≤ 10000.
Source
每次询问，相当于确定每个质数P是否出现。考虑到最坏情况，一定是问什么都回答1，否则的话就相当于把n缩小成了n/p。
问题就转换成了将1~n中间的质数分成K组，每组内的质数之积不大于n，求最小的k。
对于不小于$\sqrt n$的质数来说，他一定只能和小于$\sqrt n$的质数来配对，这样答案至少为不小于$\sqrt n$的质数个数。
而小于$\sqrt n$的质数的个数一定比不小于$\sqrt n$的质数的个数小很多，并且一定可以找到一个质数来配对。
所以问题的答案可以通过贪心来求，递减枚举每一个不小于质数，判断当前最小质数是否可以合并。
#include<cstdio>
#include<algorithm>
#define N 100010
using namespace std;
int n,prime[N],tot,ans;
bool vis[N];
void pre()
{
for(int i=;i<=n;i++)
{
if(!vis[i])prime[++tot]=i;
for(int j=;j<=tot&&i*prime[j]<=n;j++)
{
vis[i*prime[j]]=;
if(!(i%prime[j]))break;
}
}
}
int main()
{
scanf("%d",&n);
pre();
for(int l=,r=tot;l<=r;r--)
{
ans++;
int now=l,sum=prime[r];
while(l<r&&sum*prime[l]<=n)
sum*=prime[l++];
}
printf("%d\n",ans);
}