终于有一个SPOJ题目是我自己独立做出来的，ORZ，太感动了。
题目意思是给你一个素数，问你一个数r是否满足,r,r^2,r^3,……,r^p-1，全不相同。
以前做过这种类型的题目额。是这样的。
根据欧拉定理我们知道，对于任意一个x<p，我们都有 x^(p-1)==1(mod p)，这样我们只要判断x是否对于p-1的所有因数y是否都不满足 x^y!=1，如果存在等于1的情况，那说明就是NO咯。
上代码：
1 #include <cstdio> 2 #define ll long long 3 using namespace std; 4 5 ll power(ll a,ll b,ll p) 6 { 7 ll ans=1; 8 while (b) 9 { 10 if (b&1) ans=(ans*a)%p; 11 b>>=1; 12 a=(a*a)%p; 13 } 14 return ans; 15 } 16 17 bool check(ll x,ll p) 18 { 19 for (ll i=2 ;i*i<p; i++) 20 { 21 if ((p-1)%i!=0) continue; 22 if (power(x,i,p)==1) return false; 23 if (power(x,(p-1)/i,p)==1) return false; 24 } 25 return true; 26 } 27 28 int main() 29 { 30 ll n,p,x; 31 while (scanf("%lld%lld",&p,&n) && (n|p)) 32 { 33 while (n--) 34 { 35 scanf("%lld",&x); 36 x%=p; 37 if (x==0) 38 { 39 printf("NO "); 40 continue; 41 } 42 if (check(x,p)) printf("YES "); 43 else printf("NO "); 44 } 45 } 46 return 0; 47 }