spoj PROOT

テーマリンク:http://www.spoj.com/problems/PROOT/
複数のグループのデータは、あなたに素数P（p<2^31）、n個rをあげます。それぞれのrについて、rがPの原根かどうかを判断します。
テーマ分析：rはPの原根の充填条件として、Pに対する素因数p毎に、r^((P-1)/p)モールドPは1ではない。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;
const int maxn=100100;
bool valid[maxn];
int prim[maxn],pr[maxn];
int primm=0,c;   //c n       
void getPrime(int n,int &tot)    //n       ,tot     ,ans[] prim   
{
	memset(valid,true,sizeof(valid));
	for (int i=2;i<=n;i++)
	{
		if (valid[i])
		{
			tot++;
			prim[tot]=i;
			for (int j=2;j<=n/i;j++)
			  valid[i*j]=0;
		}
	}
}

void cal(LL n)
{
	LL t=n,a;
	c=0;
	for (int i=1;prim[i]*prim[i]<=n,i<=primm;i++)
	{
		if (n%prim[i]==0)
		{
			c++;
			pr[c]=prim[i];
			while (n%prim[i]==0) n/=prim[i];
		}
	}
	if (n>1)
	{
		c++;
		pr[c]=n;
	}
}
LL quick_mod(LL a,LL b,LL m)
{
	LL ans=1;
	a%=m;
	while (b)
	{
		if (b&1)
		{
			ans=ans*a%m;
			b--;
		}
		b>>=1;
		a=a*a%m;
	}
	return ans;
}

int main()
{
	LL P,t,n;
	getPrime(maxn-1,primm);
	cin>>P>>n;
	while (n+P!=0)
	{
		cal(P-1);
		for (int i=1;i<=n;i++)
		{
			LL x;
			cin>>x;
			bool flag=true;
			for (int j=1;j<=c;j++)
			{
				t=(P-1)/pr[j];
				if (quick_mod(x,t,P)==1)
				{
					flag=false;
					break;
				}
			}
			if (flag)  printf("YES
");
			    else   printf("NO
");
			
		}
		cin>>P>>n;
	} 	
	return 0;
}