学步园

http://poj.org/problem?id=4028

现在有一个数x，1 ≤ x≤ n，告诉你n，每次你可以猜一个数y，如果x==y则结束，否则返回gcd(x,y)，问最少只要几次就可以保证猜出答案。

贪心。

题解见http://blog.csdn.net/keshuai19940722/article/details/38352765

我只是实现了一下代码。。神马都不会。。。

//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive    Blog:http://willinglive.cf
************************************************/
#define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
inline const int read()
{int r=0,k=1;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;
for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';return k*r;}
/////////////////////////////////////////////////
const int N=10005;
int n;
int prim[3000],cnt;
bool flag[N];
bool vis[N];
/////////////////////////////////////////////////
void init_prim()
{
	rep(i,2,N)
	{
		if(!flag[i]) prim[++cnt]=i;
		for(int j=1;j<=cnt&&i*prim[j]<=N;j++)
		{
			flag[i*prim[j]]=1;
			if(i%prim[j]==0) break;
		}
	}
}
void set(int n,int i)
{
	if(!n) return;
	for(;i>=1;i--)
	{
		int p=prim[i];
		if(p>n||vis[p]) continue;
		vis[p]=1;
		set(n/p,i-1);
	    return;
	}
}
/////////////////////////////////////////////////
void solve()
{
	init_prim();
    while(~scanf("%d",&n))
    {
    	int ans=0;
    	MS(vis,0);
    	per(i,cnt,1)
    	{
    		int p=prim[i];
    		if(p>n||vis[p]) continue;
    		ans++;
    		vis[p]=1;
    		set(n/p,i-1);
    	}
    	printf("%d\n",ans);
    }
}
/////////////////////////////////////////////////
int main()
{
    #ifndef _TEST
    freopen("std.in","r",stdin); freopen("std.out","w",stdout);
    #endif
    solve();
    return 0;
}