SPOJ Primitive Root: 하나의 모드p의 단계가 p-1인지 아닌지 판단

Description
In the field of Cryptography, prime numbers play an important role. We are interested in a scheme called "Diffie
-Hellman"key exchange which allows two communicating parties to exchange a secret key. This method requires
 a prime numberp and r which is a primitive root of p to be publicly known. For a prime number p, r is a primitive 
root if and only if it's exponents r, r2, r3, ... , rp-1 are distinct (mod p). Cryptography Experts Group (CEG) is trying
to develop such a system. They want to have a list of prime numbers and their primitive roots. You are going to
write a program to help them. Given a prime number p and another integer r < p , you need to tell whether r is a
primitive root of p.
Input
There will be multiple test cases. Each test case starts with two integers p ( p < 2 31 ) and n (1 ≤ n ≤ 100 ) sepa
rated by a space on a single line. p is the prime number we want to use and n is the number of candidates we 
need to check. Then n lines follow each containing a single integer to check. An empty line follows each test 
case and the end of test cases is indicated by p=0 and n=0 and it should not be processed. The number of test
 cases is atmost 60.
Output
For each test case print "YES"(quotes for clarity) if r is a primitive root of p and "NO"(again quotes for clarity) otherwise.
Sample Input

Input:
5 2
3
4

7 2
3
4

0 0


Output:
YES
NO
YES
NO

In the first test case 31, 32 , 33 and 34 are respectively 3, 4, 2 and 1 (mod 5). So, 3 is a primitive root of 5.
41, 42 , 43 and 44 are respectively 4, 1, 4 and 1 respectively. So, 4 is not a primitive root of 5.
//제목: p와 n을 제시합니다.그 다음에 n개의 수를 개출하여 이 수형 p의 단계가 p-1인지 판단한다.
//에서 "멱모p와 원근"장에서 언급한 단계의 개념은 다음과 같다.
만약 a가 소수p에 의해 제거되지 않는다면, a모드p의 단계는
a^e=1(modp)의 최소 지수 e>=1;예를 들어 2, 3, 4, 5, 6모드 7의 단계는 각각 3, 6, 3, 6, 2이다.그리고 본 장에서
몇 가지 중요한 성질을 제시하는데 그 중에서 다음과 같다.
하나의 수 a모드p의 단계 e는 항상 p-1을 제거할 수 있다.그래서 p-1의 인자factor를 일일이 들 수 있어요.
(p-1 포함), p-1보다 작은 인자 만족 a^factor=1(modp)이 존재하면 a모드p의 단계는 p-1이 아니라는 것을 설명한다.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<algorithm>
#include<ctime>
using namespace std;
#define maxn 65560
#define LL __int64

int factor[maxn];
LL mod_exp(LL a,LL r,LL p)
{
	LL d=1;
	a%=p;
	while(r)
	{
		if(r&1) d=d*a%p;
		a=a*a%p;
		r>>=1;
	}
	return d%p;
}

int main()
{
	int p,n,x;
	while(~scanf("%d%d",&p,&n),p|n)
	{
		int cnt=0,i;
		for(i=2;i<=(int)sqrt(1.0*(p-1));i++)
			if((p-1)%i==0)
				factor[++cnt]=i,factor[++cnt]=(p-1)/i;
		while(n--)
		{	
			bool flag=true;
			scanf("%d",&x);
			for(i=1;i<=cnt;i++)
				if(mod_exp(x,factor[i],p)==1) // p-1 a^factor=1（mod p）
				{
					flag=false;
					break;
				}
			printf("%s
",flag?"YES":"NO");
		}
	}
	return 0;
}