• NTT预备知识，下一个要填的坑就是NTT！

• 本文为博主原创，未经许可不得转载

整数的次数

定义

若$gcd(a,p)=1$，使得$a^x\equiv 1 (mod p)$成立的最小的正整数$x$称为$a模p的次数$，记作$Ord_p a$

定理一

若正整数n满足$a^n\equiv 1 (mod p)$，则$Ord_p a|n$

证明：
假设结论不成立，记$x=Ord_p a$，那么必有两整数$k,r$，使得$n=kx+r$且$0<r<x$
而$a^n=a^{kx+r}=a^{kx}\times a^r \equiv 1(mod p)$
故$a^r\equiv 1 (mod p)$
这与$x$的定义相违背，故定理成立

由上述定理易得如下推论：$Ord_p a|\phi(p)$

解释：
由欧拉定理，必有$a^{\phi(p)}\equiv 1(mod p)$
所以推论成立

定理二

设$x=Ord_p a$，则$1,a,a^2,…,a^x-1$模$m$两两不同余

证明：
假设结论不成立，则必有某对$j,k$满足$0<=j<k<x$，使得$a^j\equiv a^k(mod p)$
则有$a^{k-j}\equiv 1(mod p)$，而$0<k-j<x$，这与$x$的定义相矛盾
故定理成立

原根

定义

若$Ord_p g=\phi(p)$，则称$g$为$m$的一个原根

求法

$Ord_p g=\phi(p)$的意思就是满足方程$g^x \equiv 1(mod p)$的最小的$x$是$\phi(p)$

而$g^{\phi(p)} \equiv 1(mod p)$是一定成立的

那么我们的思路就是从$2到n-1$枚举$g$，检验$g^x \equiv 1(mod p)$在区间$1<x<\phi(p)$上恒不成立即可

而根据定理一，满足$g^x \equiv 1(mod p)$的x一定是$\phi(p)$的约数，所以我们只需要枚举$\phi(p)$的因子即可

参考代码

• 【51nod1135】原根 传送门

1
2
3
4
5
6
7
8
9
10
11
12
13

int Proots(int n){
	int temp=n-1,top(0);
	for(int i=2;i*i<=n;++i)if(temp%i==0){
		sta[++top]=i;
		while(temp%i==0)  temp/=i;
	}
	if(temp>1) sta[++top]=temp;
	for(int i=2;i<n;++i){
		int flag=1;
		for(int j=1;j<=top;++j)if(power(i,(n-1)/sta[j],n)==1){flag=0;break;}
		if(flag)  return i;
	}
}

参考文献

• 《从傅里叶变换到数论变换》——Menci 传送门
• 《数论讲义》