HDU1286_找新朋友_筛选法

题目大意：          让你输入一个数n,求1……n-1这么多个数，能与n有公约数不为1的数的总数。 解题思路：          while里面有一个小技巧。一开始用一般的gcd()函数调用方法，就直接TLE了。打表也TLE。 代码：

#include
using namespace std;
const int MAX=32769;
int gcd(int a,int b)
{
	int c;
	while(b)
	{
		c=a%b;
		a=b;
		b=c;
	}
	return a;
}
int hash[MAX];
int main(void)
{
	int n,num;
	cin>>n;
	while(n--)
	{
		int count=0;
		cin>>num;
		memset(hash,0,sizeof(hash));
		for(int i=2;i