[笔记] 求质数的原根

素数的原根的定义：若/(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;
  }
}