建议与上一篇欧拉函数介绍结合食用。

知识点:

1.阶：a和模m互质，使a^d≡1(mod m)成立的最小正整数d称为a对模m的阶(指数)

   例如：

　　2^2≡1(mod3),2对模3的阶为2;

　　2^3≡1(mod7),2对模7的阶为3;

2.欧拉函数φ(m)：在[1,m)的区间内与m互质的数的个数。可见前一篇blog

3.设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。

求模素数p的原根a的方法：

对质数 p, φ(p) = p-1, 这题就是要找最小的a使得 a^(p-1)%p = 1 成立（根据费马小定理，该式一定成立，且a可取大于 1 的任意整数），所以只需要验证没有比 p-1 小的数 k 令 a^k%p = 1 。

而 k 不需要全部枚举 ，只需枚举 p-1 除去1和它本身的质因子即可。（如果x为p-1的质因子，且a^x%p = 1,那么x的倍数nx显然也满足a^nx%p = 1 ，所以没必要考虑了。反之同理。）

所以重点就到回到了找质因子上，1e9，还是筛。

参考了很多dalao的博客，但链接没记下来，不好意思。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #define maxn 50000 5 using namespace std; 6 typedef long long ll; 7 int prime [maxn];//存素数 8 int ppri [maxn];//存p-1的质因子 9 void getprime(){
    //打表10     int cnt = 0;11     memset(prime,0,sizeof(prime));12     for(int i=2;i
         
          0){20         if(n%2) res=res*x%mod;21         x=x*x%mod;22         n/=2;23     }24     return res;25 }26 27 int divide(int n){
    //分解n的质因子28     int cnt=0;29     for(int i = 1; prime[i] * prime[i] <= n; ++i){30         if(n % prime[i] == 0)  ppri[++cnt]=prime[i];31         while(n % prime[i] == 0)  n/=prime[i];32     }33     return cnt;34 }35 36 int main(){37     int p,a,t,flag,cnt;38     cin>>p;39     getprime();40     cnt=divide(p-1);//p-1 的质因子个数41     for(a = 2; a <= p - 1; ++a){
    //a 从 2 到 p-1 枚举42         flag=1;43         for(int i=1; i <= cnt; ++i){44             t = (p - 1) / ppri[i];45             if(pow(a, t, p)==1){46                 flag=0;47                 break;48             }49         }50         if(flag){51             cout<
          <