素数的原根的定义：若/(g^0,g^1 /cdots g^{p-1}/)在mod p意义下各不相同，则g是p的一个原根。质数的最小的原根通常很小，所以从2开始枚举每一个正整数，判断其是否为p的原根。
判断的方法：如果g不是p的原根，则存在/(0/leq i < j /leq p-1/)满足/(g^i≡g^j/)(mod p)，也就是存在d(/(0<d /leq p-1/)),使得/(g^d≡1/)(mod p)。
(接下来的内容请感性理解，不做说明。这种东西把实现方法背下来就行了)
/(g^{p-1}≡1/)，所以/(d|p-1/)。最后的做法是，令/(P_1 /cdots P_n/)表示p-1的质因数集合，对于每一个/(P_i/)，判断/(g^{/frac{p-1}{P_i}}/)是否与1同余，如果是，则g不合法。如果没有导致不合法的/(P_i/)，则g合法。
代码如下：
点击查看代码
LL getG()
{
vector <LL> ps;
LL lft=p-1;
for(LL i=2;i*i<=lft;++i) if(lft%i==0)
{
ps.pb(i);
while(lft%i==0) lft/=i;
}
if(lft>1) ps.pb(lft);
rep(i,ps.size()) ps[i]=(p-1)/ps[i];
for(LL i=2;;++i)
{
bool ok=true;
rep(j,ps.size()) if(qpow(i,ps[j],p)==1)
{
ok=false;
break;
}
if(ok) return i;
}
}
原创文章，作者：254126420，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/272264.html