转:http://hzwer.com/1645.html
Description
K国在胖哥的英明统治下,近来迷上了一款非常脑残的游戏,叫做猜数字,这个游戏是一个二人游戏,胖哥认为它非常有利于促进两个人之间的感情,假设玩家A和玩家B进行这个游戏,首先他们会确定一个正整数n,然后A从1-n中选定一个整数,注意一旦选定之后只有游戏结束都不能修改这个数字,假设这个数字是x,然后游戏开始,每次B都可以在1-n中选择一个整数,假设这个数字是y,然后A会告诉他gcd(x,y)的值,即x和y的最大公约数,B可以利用之前A回答的结果决定每一轮中他所选择的数字,如果在某一时刻,B可以用A回答的结果推理出A选择的数字,则游戏结束,假设n=6,如果A选定了数字2,然后第一轮B询问了数字6,A回答2,这时B可以推断出A手中的数字只能是2或者4,然后B询问数字2就可以知道A手中的数字了(这只是一种可能的游戏进行方式,可能并非最优策略),作为K国的国王,胖哥已经疯狂的迷恋上了这个游戏,他想要知道,对于一个确定的正整数n,在最坏的情况下游戏会进行几轮,即无论A选择了什么数字,B都可以保证有一个策略使得游戏在这么多轮之内结束,可以游戏双方都遵循最优策略进行,同时你可以认为K国的国民都十分诚实,他们一旦选定了数字之后就永远不会改变
Input
首先输入一个数Q,表示有Q(Q ≤ 10)组样例
每组样例首先输入一个整数n (2 ≤ n ≤ 10000),表示在这组样例中游戏前确定的正整数n
Output
对于每组样例,首先输出样例编号,之后输出在最优策略下,最坏的情况需要询问几次,具体格式见sample output
Sample Input
4
2
3
5
6
Sample Output
Case 1: 1
Case 2: 2
Case 3: 3
Case 4: 2
数据范围:
样例 n
1 ≤ 10
2 ≤ 20
3 ≤ 50
4 ≤ 100
5 ≤ 200
6 ≤ 1000
7 ≤ 10000
8 ≤ 10000
9 ≤ 10000
10 ≤ 10000
贪心策略
若想知道对方手中的数字。需要确定是否存在《=n的每一个质数
如n=10,要分别确定2,3,5,7
首先的想法是把小的质数放在一起问
但是发现大质数每个依然要问一次
所以应该把大质数后小质数一起问
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int T,n,ss[2000],cnt;
bool pd[2000];
bool prime(int x){for(int i=1;i<=cnt;i++)if(x%ss[i]==0)return 0;return 1;}
void build(){for(int i=2;i<=10000;i++)if(prime(i)){ss[++cnt]=i;}}
int main()
{
scanf("%d",&T);
build();
for(int l=1;l<=T;l++)
{
memset(pd,0,sizeof(pd));
printf("Case %d: ",l);
scanf("%d",&n);
int ans=0,temp;
int j,k=1;
for(int i=1;i<=n;i++)if(ss[i]>n){j=i-1;break;}
for(int i=j;i>0;i--)
{
if(pd[i])continue;
if(ss[k]*ss[i]<=n){pd[k]=1;k++;}
pd[i]=1;ans++;
}
printf("%d\n",ans);
}
return 0;
}