求原根

求p的原根：

① 對p-1分解質因數 p-1=p1^k1*p2^k2……

② 從2開始枚舉g，若g滿足 g^【φ（p）/pi】！=1 對所有的 pi成立

則g為p的的一個原根

#include<cstdio>
#include<cmath>
using namespace std;
int p,tot;
int a[10000005];
void factor(int n,int &tot)
{
    int tmp,now;
    tmp=(int)((double)sqrt(n)+1);
    tot=0;
    now=n;
    for(int i=2;i<=tmp;i++)
     if(now%i==0)
      {
          a[++tot]=i;
          while(now%i==0) now/=i;
      }
    if(now>1) a[++tot]=now;
}
long long quickpow(long long x,long long n)
{
    long long ret=1;
    for(;n;n>>=1,x=(x*x)%p)
     if(n&1) ret=ret*x%p;
    return ret;
}
bool check(int g)
{
    for(int i=1;i<=tot;i++)
     if(quickpow((long long)g,(long long)(p-1)/a[i])==1) 
      return 0;
    return 1;
}
int solve(int p)
{
     for(int i=2;i<p;i++)
      if(check(i)) return i;
}
int main()
{
    scanf("%d",&p);
    factor(p-1,tot);
    printf("%d",solve(p));
}      

作者：xxy

本文版權歸作者有，轉載請用連結，請勿原文轉載，Thanks♪(･ω･)ﾉ。