求质数的原根

#include <bits/stdc++.h>
using namespace std;
const int N=1000005;
int P, cnt, pcnt, p[N], pr[N];
bool np[N];
typedef long long ll;
int gcd(int a, int b) { return b?gcd(b, a%b):a; }
int ipow(int a, int b) { int x=1; for(; b; b>>=1, a=(ll)a*a%P) if(b&1) x=(ll)x*a%P; return x; }
bool check(int d) {
	if(gcd(d, P)!=1) return 0;
	for(int i=1; i<=cnt; ++i) if(ipow(d, (P-1)/pr[i])==1) return 0;
	return 1;
}
void init() {
	for(int i=2; i<N; ++i) {
		if(!np[i]) p[++pcnt]=i;
		for(int j=1; j<=pcnt; ++j) {
			int t=i*p[j]; if(t>=N) break; np[t]=1;
			if(i%p[j]==0) break;
		}
	}
}
void get() {
	int temp=P-1;
	for(int i=1; i<=pcnt && p[i]*p[i]<=temp; ++i) if(temp%p[i]==0) { while(temp%p[i]==0) temp/=p[i]; pr[++cnt]=p[i]; }
	if(temp>1) pr[++cnt]=temp;
}
int main() {
	scanf("%d", &P);
	init();
	get();
	for(int i=2; i<P; ++i) if(check(i)) { printf("%d\n", i); break; }
	return 0;
}

　　

如果$(a, m)=1$，那么容易得到$\delta_{m} (a) | \varphi(m)$，因此我们只需要检测$m$的约数即可，可是复杂度很高= =。

更特殊的，假如$m$是质数，那么我们只需要检测$\frac{\varphi(m)}{p_1}, \frac{\varphi(m)}{p_2}, \cdots, \frac{\varphi(m)}{p_k}$（$p_i$表示$\varphi(m)$的不同的质因子）即可。

证明：

如果检测出来时，显然$a$不是原根。否则，我们没有检测出来，即$a$不是$m$的原根，令$d<\varphi(a)$使得$a^d \equiv 1 \pmod{m}$

因为$d<\varphi(m)$，所以$(d, \varphi(m)) < \varphi(m)$。

而又因为$(d, \varphi(m)) | \varphi(m)$, 所以$(d, \varphi(m))$必整除$\frac{\varphi(m)}{p_1}, \frac{\varphi(m)}{p_2}, \cdots, \frac{\varphi(m)}{p_k}$中至少一个，令其中一个为$\frac{\varphi(m)}{p_i}$。

由于存在$x, y$使得$dx+\varphi(m)y = (d, \varphi(m))$，所以$a^{(d, \varphi(m))} \equiv (a^d)^x (a^{\varphi(m)})^y \equiv 1 \pmod{m}$。

所以$a^{\frac{\varphi(m)}{p_i}} = (a^{(d, \varphi(m))})^{t} \equiv 1 \pmod{m}$。

与我们没有检测出来的假设矛盾。

故结论得证。

由于质因数分解出来很小，故复杂度我们可以认为是$O(nlog^2n)$，而又因为质数的原根都非常小= =所以...整体来看就是一个常数！