一个数m如果有原根，则其原根个数为phi(phi(m))。特别地，对素数有phi(p)=p-1。
假设g是奇素数p的一个原根，则g^1,g^2,...,g^(p-1)在模p意义下两两不同，且结果恰好为1~p-1，由此可以定义“离散对数”，与连续数学中的对数有异曲同工之妙。
离散对数又叫做“指标”，有指标法则：I(ab)≡I(a)+I(b) (mod p-1)；I(a^k)≡k*I(a) (mod p-1)，由此可以把乘法转化为加法。
指标的求法：
#includeusing namespace std;bool notpri[100005];int pri[100005],zyz[100005];typedef long long ll;void Shai(int N){ notpri[1]=1; for(int i=2;i<=N;++i){ if(!notpri[i]){ pri[++pri[0]]=i; } for(int j=1;j<=pri[0] && (ll)i*(ll)pri[j]<=N;++j){ notpri[i*pri[j]]=1; if(i%pri[j]==0){ break; } } }}ll Quick_Pow(ll x,ll p,ll mod){ if(!p){ return 1ll; } ll res=Quick_Pow(x,p>>1,mod); res=res*res%mod; if((p&1ll)==1ll){ res=(x%mod*res)%mod; } return res;}int FindRoot(int x){/*求素奇数的最小原根，倘若x不是奇数，但是也有原根的话，将质因子分解改成对phi(x)即可。倘若要求多个原根，直接接着暴力验证即可*/ int tmp=x-1; for(int i=1;tmp && i<=pri[0];++i){ if(tmp%pri[i]==0){ zyz[++zyz[0]]=pri[i]; while(tmp%pri[i]==0){ tmp/=pri[i]; } } } for(int g=2;g<=x-1;++g){ bool flag=1; for(int i=1;i<=zyz[0];++i){ if(Quick_Pow((ll)g,(ll)((x-1)/zyz[i]),(ll)x)==1ll){ flag=0; break; } } if(flag){ return g; } }}int main(){ Shai(100000); printf("%d\n",FindRoot(2017)); return 0;}