首先，笔者要给大家介绍一下，什么叫原根。 设g是奇素数m的一个原根，则g1 mod m , g2 mod m , g3 mod m , … , gm-1 mod m 两两不同。并且其结果恰好为1 ~ m-1。

---

下面是原根的求法以及其性质：

• 模数m有原根当且仅当 m = 2,4,pa, 2*pa这四种。其中p是奇素数。
• 求素数m原根的方法：对m-1进行质因数分解，即m-1 =
  p1a1p2a2p3a3…pkak，若恒有g(m-1)/pi != 1(mod m) 成立，则g就是m的原根。
  （对于合数求原根，只需把m-1换成phi(m)即可）。 聪明的读者已经发现了，phi(m) = m-1 当 m是素数。
• 原根的性质：如果一个数m有原根，其原根的个数为phi(phi(m))。

代码如下： #include using namespace std; const int maxn = 1e7+7; int pri[maxn],ispri[maxn],divi[maxn]; int p = 2019; int qpow(int a,int b) { int ans = 1; while(b>0) { if(b&1) ans = ans*a%p; b>>=1; a = a*a%p; } return ans%p; } void getprime() { memset(ispri,1,sizeof(ispri)); ispri[0] = ispri[1] = 0; for(int i=2;i<maxn;i++) { if(ispri[i]) pri[++pri[0]] = i; for(int j=1;j<=pri[0] && i*pri[j]<maxn;j++) { ispri[i*pri[j]] = 0; if(i%pri[j]==0) break; } } } int findroot(int x) { int tmp = x-1; for(int i=1;i<=pri[0];i++) { if(tmp%pri[i]==0) { divi[++divi[0]] = pri[i]; while(tmp%pri[i]==0) tmp /= pri[i]; } } for(int g=2;g<=x-1;g++) { bool found = false; for(int i=1;i<=divi[0];i++) { if(qpow(g,(x-1)/divi[i])==1) { found = true; break; } } if(!found) return g; } } int main() { getprime(); printf("%d ",findroot(2019)); return 0; }