1622:判断数（快速幂+素数）

Description
给定一个n , 我们把对任意的1<x<n都有 x^n=x(mod n)成立的合数 n 称为good number。现求该数是否为good number。
Input
输入一个数 n （n<1000000）
Output
输出YES或NO
Sample Input
561
21
Sample Output
YES
NO
思路：快速幂运用+素数判断
一直在OLE和RE中来回跳转。。。。
重点还是数组得开大不开小，还有输入不要多写。。想太多系列
附上参考https://blog.csdn.net/ZCMU_2024/article/details/81634556和https://www.cnblogs.com/murmured/p/5004067.html两位巨巨，感谢！！

#include<vector>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#include<stdlib.h>

using namespace std;
typedef long long ll;
const int maxn=1000005;
bool a[maxn];int n;
ll pow(ll a,ll b,ll mod){//快速幂 
    ll sum=1;
    while(b){
        if(b&1) sum=sum*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return sum;
}
int main(){
    memset(a,0,sizeof(a));
    //素数判断 
    for(int i=2;i<=maxn;i++){
            for(int j=i*2;j<=maxn;j+=i)
                a[j]=1;
    }
    //
    while(~scanf("%d",&n))
    {
        bool flag=true;
        if(!a[n]) flag=false;
        if(flag)
            for(ll i=2;i<n;i++)
            {
                ll temp=pow(i,n,n);
                if(temp!=i){
                    flag=false;
                    break;
                }
            }
        
        if(flag)printf("YES\n");
        else printf("NO\n");    
    } 

     return 0;
}