原根

阶

定义

设 $m>1$ 且 $\gcd(a,m)=1$，那么使得 $a^r \equiv 1 \pmod m$ 成立的最小正整数 $r$ 称为 $a$ 对模 $m$ 的阶，记为 $\delta_m(a)$。

性质

性质 1

设 $m>1$ 且 $\gcd(a,m)=1$，$a^n \equiv 1 \pmod p$，则 $\delta_m(a)|n$。

反证法，假设 $n=\delta_m(a) \times x+y$，$0<y<\delta_m(a)$。则 $a^n \equiv a^{\delta_m(a) \times x} \times a^y \equiv a^y \equiv 1$，矛盾。

性质 2

$\delta_m(a)|\varphi(m)$。

因 $a^{\varphi(m)} \equiv 1 \pmod m$，由性质 1 可证。

性质 3

若 $\gcd(a,m)=1$，则 $a^x \equiv a^y \pmod m$ 的充要条件是 $x \equiv y \pmod {\delta_m(a)}$。

充分性：条件转化为 $x=k \times \delta_m(a)+y$，则 $a^x \equiv a^{k \times \delta_m(a)+y} \equiv a^y \pmod m$。

必要性：根据消去律，$a^{x-y} \equiv 1 \pmod m$，根据性质 1，$\delta_m(a)|(x-y)$，可得 $(x-y)=k\delta_m(a) \Rightarrow x \equiv y \pmod {\delta_m(a)}$。

性质 4

对于正整数 $d$，$\delta_m(a^d)=\dfrac{\delta_m(a)}{\gcd(\delta_m(a),d)}$。

令 $t=\gcd(\delta_m(a),d)$，$\delta_m(a)=p \times t$，$d=q \times t$（$\gcd(p,q)=1$）。

根据定义，$\delta_m(a^d)$ 是满足 $(a^d)^x=a^{qtx} \equiv 1 \pmod m$ 的最小的 $x$。

由性质 1，$\delta_m(a)|qtx \Rightarrow pt|qtx \Rightarrow p|qx \Rightarrow p|x \Rightarrow x=p \Rightarrow \delta_m(a^d)=\dfrac{\delta_m(a)}{\gcd(\delta_m(a),d)}$。

性质 5

设 $n>1$，$a,b,m \in \mathbb{Z}$，$\gcd(a,m)=\gcd(b,m)=1$，则 $\delta_m(ab)=\delta_m(a)\delta_m(b)$ 的充要条件是 $\gcd(\delta_m(a),\delta_m(b))=1$。

必要性：由于 $a^{\delta_m(a)} \equiv 1 \pmod m$ 和 $b^{\delta_m(b)} \equiv 1 \pmod m$，有 $(ab)^{\operatorname{lcm}(\delta_m(a),\delta_m(b))} \equiv 1 \pmod m$。由性质 1，有 $\delta_m(ab)|\operatorname{lcm}(\delta_m(a),\delta_m(b))$。又因为 $\delta_m(ab)=\delta_m(a)\delta_m(b)$，所以 $\delta_m(a)\delta_m(b)|\operatorname{lcm}(\delta_m(a),\delta_m(b))$，$\gcd(\delta_m(a),\delta_m(b))=1$。

充分性：由 $(ab)^{\delta_m(ab)} \equiv 1 \pmod m$ 得 $1 \equiv (ab)^{\delta_m(ab)\delta_m(b)} \equiv a^{\delta_m(ab)\delta_m(b)}b^{\delta_m(ab)\delta_m(b)} \equiv a^{\delta_m(ab)\delta_m(b)}$，故 $\delta_m(a)|\delta_m(ab)\delta_m(b)$，由于 $\gcd(\delta_m(a),\delta_m(b))=1$，所以 $\delta_m(a)|\delta_m(ab)$。

同理，有 $\delta_m(b)|\delta_m(ab)$。因此，有 $\delta_m(a)\delta_m(b)|\delta_m(ab)$。

另一方面，有 $(ab)^{\delta_m(a)\delta_m(b)} \equiv (a^{\delta_m(a)})^{\delta_m(b)}(b^{\delta_m(b)})^{\delta_m(a)} \equiv 1 \pmod m$。所以，$\delta_m(ab)|\delta_m(a)\delta_m(b)$。

综合以上两点得到 $\delta_m(ab)=\delta_m(a)\delta_m(b)$。

原根

定义

设 $m$ 为正整数，$a$ 为整数，如果 $\delta_m(a)=\varphi(m)$，那么称 $a$ 为模 $m$ 的一个原根。

原根存在的条件

结论

一个正整数 $m$ 有原根的充要条件是 $m=2,4,p^r,2p^r$，其中 $p$ 为奇素数，$r$ 为正整数。

前置知识：拉格朗日定理

拉格朗日定理：若 $p$ 为素数，对于模 $p$ 意义下的整系数多项式 $f(x)=\sum\limits_{i=0}^na_ix^i$ 的同余方程 $f(x) \equiv 0 \pmod p$ 在模 $p$ 意义下至多有 $n$ 个不同解。

证明：使用数学归纳法。$n=0$ 时，由于 $p\not|a_0$，故 $f(x) \equiv 0 \pmod p$ 无解，定理对 $n=0$ 的多项式 $f(x)$ 都成立。

若命题对于 $\operatorname{deg}(f)<n$ 的 $f$ 都成立，用反证法，结社存在一个满足题目条件的 $f$ 在模 $p$ 意义下有着至少 $n+1$ 个不同的解 $x_0,x_1,\cdots,x_n$。可设 $f(x)-f(x_0)=(x-x_0)g(x)$，则 $g(x)$ 在模 $p$ 意义下是一个至多 $n-1$ 次的多项式。现在由 $x_0,x_1,\cdots,x_n$ 都是 $f(x) \equiv 0 \pmod p$ 的解，则对于所有 $1 \le i \le n$，都有 $(x_i-x_0)g(x_i) \equiv f(x_i)-f(x_0) \equiv 0 \pmod p$，而 $x_i \not\equiv x_0 \pmod p$，故 $g(x_i) \equiv 0 \pmod p$，从而 $g(x) \equiv 0 \pmod p$ 至少有 $n$ 个根，与归纳假设矛盾。

所以，命题对 $n$ 次多项式也成立，定理获证。

定理 1：对于奇素数 $p$，$p$ 有原根。

引理：设 $a$ 与 $b$ 是与 $p$ 互素的两个整数，则存在 $z \in \mathbb{Z}$ 使得 $\delta_p(c)=\operatorname{lcm}(\delta_p(a),\delta_p(b))$。

记 $r=\delta_p(a)$，$t=\delta_p(b)$

设 $d=\gcd(r,t)$，$x=\dfrac{r}{d}$，则 $\operatorname{lcm}(r,t)=xt$。由阶的性质 4，得到 $\delta_p(a^d)=\dfrac{\delta_p(a)}{\gcd(\delta_p(a),d)}=\dfrac{r}{\gcd(r,d)}=\dfrac{r}{d}=x$。

而 $\delta_p(b)=t$，$\gcd(x,t)=1$，由阶的性质 5，得到 $\delta_p(a^db)=xt$，引理得证。

回到原命题，利用上述引理，结合数学归纳法，可知存在 $g \in \mathbb{Z}$，使得 $\delta_p(g)=\operatorname{lcm}(\delta_p(1),\delta_p(2),\cdots,\delta_p(p-1))$。

这表明 $\forall 1 \le i \le p-1,\delta_p(i)|\delta_p(g)$，所以 $i=1,2,\cdots,p-1$ 都是 $x^{\delta_p(g)} \equiv 1 \pmod p$ 的根。由拉格朗日定理，可得 $\delta_p(g) \ge p-1$。另一方面，由费马小定理知 $g^{p-1} \equiv 1 \pmod p$，故有 $\delta_p(g)|p-1$。

因此，$\delta_p(g)=p-1$，即 $g$ 为模 $p$ 的原根。

定理 2：对于奇素数 $p$，$\alpha \in \mathbb{N}^*$，$p^\alpha$ 有原根。

引理：存在模 $p$ 的原根 $g$，使得 $g^{p-1} \not\equiv 1 \pmod {p^2}$。

事实上，任取模 $p$ 的原根 $g$，若 $g$ 不满足条件，那么 $g+p$ 满足条件。

$$\begin{aligned} (g+p)^{p-1} &\equiv C_{p-1}^0g^{p-1}+C_{p-1}^1pg^{p-2} \\ &\equiv g^{p-1}+p(p-1)g^{p-2} \\ &\equiv 1-pg^{p-2} \\ &\not\equiv 1 \pmod {p^2} \end{aligned}$$

回到原题，我们可以证明若 $g$ 满足引理，则对于任意 $\alpha \in \mathbb{N}^*$，$g$ 是模 $p^\alpha$ 的原根。

用数学归纳法。

首先，$\alpha=1$ 时，显然有 $g^{\varphi(p^\alpha)}=g^{p-1}=1+p^\alpha \times k_\alpha$，其中 $p\not|k_\alpha$。

假设 $\alpha=\beta$ 时结论成立，那么当 $\alpha=\beta+1$ 时，有：

$$\begin{aligned} g^{\varphi(p^{\beta+1})} &= (g^{\varphi(p^\beta)})^p \\ &= (1+p^\beta \times k_\beta)^p \\ &\equiv 1+p^{\beta+1} \times k_\beta \\ &\not\equiv 1 \pmod {p^{\beta+2}} \end{aligned}$$

命题仍然成立。

所以命题对于任意 $\alpha \in \mathbb{N}^*$ 成立。

由欧拉定理以及阶的性质 2，有 $\delta_{p^\alpha}(g)|p^{\alpha-1}(p-1)$。

又因为 $g$ 为模 $p$ 的原根，以及 $g^\delta_{p^\alpha}(g) \equiv 1 \pmod {p^\alpha}$，可以知道 $(p-1)|\delta_{p^\alpha}(g)$。

因此可以设 $\delta_{p^\alpha}(g)=p^{\beta-1}(p-1)$，其中 $1 \le \beta \le \alpha$。

我们发现 $g^{\varphi(p^\beta)} \not\equiv 1 \pmod {p^{\beta+1}} \Rightarrow g^{\delta_{p^\alpha}(g)} \not\equiv 1 \pmod {p^{\beta+1}}$。

结合 $g^{\delta_{p^\alpha}(g)} \equiv 1 \pmod {p^\alpha}$ 可知 $\beta \ge \alpha$。

因此，$\beta=\alpha$，即 $\delta_{p^\alpha}(g)=p^{\alpha-1}(p-1)=\varphi(p^\alpha)$。从而，$g$ 是模 $p^\alpha$ 的原根。

定理 3：对于奇素数 $p$，$\alpha \in \mathbb{N}^*$，$2p^\alpha$ 有原根。

设 $g$ 是模 $p^\alpha$ 的原根，则 $g+p^\alpha$ 也是模 $p^\alpha$ 的原根。在两个数之中，必定恰好有一个是奇数，设它为 $G$，则 $\gcd(G,2p^\alpha)=1$。

由阶的性质 2，$\delta_{2p^\alpha}(G)|\varphi(2p^\alpha)$。

而 $G^{\delta_{2p^\alpha}(G)} \equiv 1 \pmod {2p^\alpha}$，故 $G^{\delta_{2p^\alpha}(G)} \equiv 1 \pmod {p^\alpha}$。

因为 $G$ 是模 $p^\alpha$ 的原根，$\varphi(p^\alpha)|\delta_{2p^\alpha}(G)$。

又因为 $\varphi(p^\alpha)=\varphi(2p^\alpha)$，$G$ 是模 $2p^\alpha$ 的原根。

定理 4：对于一个大于 $1$ 的整数 $m$，若 $m \not\in \{2,4\}$ 且不存在奇素数 $p$ 以及 $\alpha \in \mathbb{N}^*$ 使得 $m \in \{p^\alpha,2p^\alpha\}$，则对于任意 $a \in \mathbb{Z}$ 且 $\gcd(a,m)=1$，都有 $\delta_m(a)<\varphi(m)$，即模 $m$ 的原根不存在。

对于 $m=2^\alpha$，$\alpha \in \mathbb{N}^*$，$\alpha \ge 3$，对任意奇数 $a=2k+1$ 均有：

$$\begin{aligned} a^{2^{\alpha-2}} &= (2k+1)^{2^{\alpha-2}} \\ &\equiv 1+C_{2^{\alpha-2}}^1(2k)+C_{2^{\alpha-3}}^2(2k)^2 \\ &\equiv 1+2^{\alpha-1}k+2^{\alpha-1}(2^{\alpha-2}-1)k^2 \\ &\equiv 1+2^{\alpha-1}(k+(2^{\alpha-2}-1)k^2) \\ &\equiv 1 \pmod {2^\alpha} \end{aligned}$$

其中最后一步用到 $k$ 与 $k^2$ 同奇偶，以及 $2^{\alpha-2}-1$ 为奇数。

若 $m$ 不是 $2$ 的正整数次幂，则设 $m=rt$，其中 $2<r<t$ 且 $\gcd(r,t)=1$。

此时，若 $\gcd(a,m)=1$，由欧拉定理的到 $a^{\varphi(r)} \equiv 1 \pmod r$，$a^{\varphi(t)} \equiv 1 \pmod t$。

注意到 $n>2$ 时 $\varphi(n)$ 为偶数，所以 $a^{\frac{1}{2}\varphi(r)\varphi(t)} \equiv 1 \pmod {rt}$。

进而 $\delta_m(a) \le \dfrac{1}{2}\varphi(r)\varphi(t)=\dfrac{1}{2}\varphi(rt)=\dfrac{1}{2}\varphi(m)<\varphi(m)$。

因此，这样的 $m$ 不存在原根。

性质

性质 1

若 $g$ 是模 $m$ 的原根，则 $g^d$ 是模 $m$ 的原根的充要条件是 $\gcd(d,\varphi(m))=1$。

由阶的性质 4 易证。

性质 2

每一个有原根的正整数 $m$ 有 $\varphi(\varphi(m))$ 个原根，每个素数都有 $\varphi(p-1)$ 个原根。

设 $g$ 是模 $m$ 的一个原根，则所有的 $a \in \mathbb{Z}$ 且 $\gcd(a,m)=1$，均存在一个唯一的自然数 $x$ 使得 $0 \le x<\varphi(m)$ 且 $g^x \equiv a \pmod m$。对于所有的 $0 \le y<\varphi(m)$ 且 $\gcd(y,\varphi(m))=1$，均有 $g^x \equiv (g^y)^{x \cdot y^{-1}} \pmod m$（其中 $y^{-1}$ 表示 $y$ 在模 $\varphi(m)$ 意义下的逆元），也就是说 $g^y$ 也是模 $m$ 的一个原根。而对于不满足 $\gcd(y,\varphi(m))=1$ 的 $y$，就有 $(g^y)^{\frac{\varphi(m)}{\gcd(y,\varphi(m))}} \equiv 1 \pmod m$，就是 $\delta_m(g^y) \le \dfrac{\varphi(m)}{\gcd(y,\varphi(m))}<\varphi(m)$，$g^y$ 就不是模 $m$ 的原根。显然，满足条件的 $y$ 有 $\varphi(\varphi(m))$ 个，这就是原根的数量。

性质 3

若 $g$ 是模 $m$ 的一个原根，则 $g,g^2,\cdots,g^{\varphi(m)}$ 对 $m$ 取模的非负最小剩余就是小于 $m$ 且与 $m$ 互质的 $\varphi(m)$ 个数的一个排列。

性质 4

$m>1$，$\varphi(m)$ 的所有不同的质因数为 $p_1,p_2,\cdots,p_k$，$\gcd(g,m)=1$，则 $g$ 是 $m$ 的原根的充要条件是 $\forall i \in [1,k] \cap \mathbb{Z},g^{\frac{\varphi(m)}{p_i}} \not\equiv 1 \pmod m$。

模板题：Luogu P6091

提交记录备份

原根表

举例：对所有 $8000$ 以内的质数打表，可以结合质数表和原根表，前者用 short 类型，后者用 char 类型（原数值 + $48$ 对应着新字符），查询时先用 std::lower_bound 找到编号，再取对应位置的答案。本例可用于 SDOI2015D1T3。

本做法参照了福利：更好的原根表 - 洛谷 | 计算机科学教育新生态，本人重新实现了代码。

#include<algorithm>
#include<cstdio>
#include<vector>
namespace IO{
	const int ARR_SIZE=1<<24;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	char input[ARR_SIZE],*si=input,*ti=input;
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	template<typename T>
	void read(T&num){
		int ch=gc();
		num=0;
		while(ch<48||ch>57)ch=gc();
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
	}
	template<typename T>
	void write(T a){
		static int ch[50],cnt=0;
		if(a==0)pc('0');
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
	void putstr(const char*str){
		while(*str!='\0')pc(*(str++));
	}
}
using IO::read;
using IO::write;
using IO::putstr;
template<typename T>
T gcd(const T a,const T b){
	return b?gcd(b,a%b):a;
}
typedef long long ll;
ll qpow(ll a,int x,const ll P){
	ll ans=1;
	while(x){
		if(x&1)ans=ans*a%P;
		a=a*a%P;
		x>>=1;
	}
	return ans;
}
const int maxval=8000,maxcnt=1007;
bool flag[maxval+1];
int p[maxcnt+1],cnt,phi[maxval+1],T,n,g,ans[maxcnt+1];
std::vector<int>factor[maxval+1];
void init(const int n){
	phi[1]=1;
	for(int i=2;i<=n;i++){
		if(!flag[i]){
			p[++cnt]=i;
			phi[i]=i-1;
			factor[i].push_back(i);
		}
		for(int j=1,target;j<=cnt&&(target=i*p[j])<=n;j++){
			flag[target]=true;
			factor[target].assign(factor[i].begin(),factor[i].end());
			if(factor[target].back()!=p[j])factor[target].push_back(p[j]);
			const int tmp=i/p[j];
			if(i==tmp*p[j]){
				phi[target]=phi[i]*p[j];
				break;
			}else phi[target]=phi[i]*(p[j]-1);
		}
	}
}
bool judge(const int x){
	for(int i:factor[phi[n]])
		if(qpow(x,phi[n]/i,n)==1)
			return false;
	return true;
}
void solve(int id){
	g=1;
	while(gcd(g,n)>1||!judge(g))g++;
	ans[id]=g;
}
int main(){
	init(maxval);
	for(int i=1;i<=cnt;i++)n=p[i],solve(i);
	putstr("const short p[]={");
	for(int i=1;i<=cnt;i++)write(p[i]),pc(i!=cnt?',':'}');
	putstr(";\n");
	putstr("const char g[]=\"");
	for(int i=1;i<=cnt;i++)pc(ans[i]+48);
	putstr("\";\n");
	return 0;
}

C++
const short p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,2267,2269,2273,2281,2287,2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,2689,2693,2699,2707,2711,2713,2719,2729,2731,2741,2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,2833,2837,2843,2851,2857,2861,2879,2887,2897,2903,2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,3001,3011,3019,3023,3037,3041,3049,3061,3067,3079,3083,3089,3109,3119,3121,3137,3163,3167,3169,3181,3187,3191,3203,3209,3217,3221,3229,3251,3253,3257,3259,3271,3299,3301,3307,3313,3319,3323,3329,3331,3343,3347,3359,3361,3371,3373,3389,3391,3407,3413,3433,3449,3457,3461,3463,3467,3469,3491,3499,3511,3517,3527,3529,3533,3539,3541,3547,3557,3559,3571,3581,3583,3593,3607,3613,3617,3623,3631,3637,3643,3659,3671,3673,3677,3691,3697,3701,3709,3719,3727,3733,3739,3761,3767,3769,3779,3793,3797,3803,3821,3823,3833,3847,3851,3853,3863,3877,3881,3889,3907,3911,3917,3919,3923,3929,3931,3943,3947,3967,3989,4001,4003,4007,4013,4019,4021,4027,4049,4051,4057,4073,4079,4091,4093,4099,4111,4127,4129,4133,4139,4153,4157,4159,4177,4201,4211,4217,4219,4229,4231,4241,4243,4253,4259,4261,4271,4273,4283,4289,4297,4327,4337,4339,4349,4357,4363,4373,4391,4397,4409,4421,4423,4441,4447,4451,4457,4463,4481,4483,4493,4507,4513,4517,4519,4523,4547,4549,4561,4567,4583,4591,4597,4603,4621,4637,4639,4643,4649,4651,4657,4663,4673,4679,4691,4703,4721,4723,4729,4733,4751,4759,4783,4787,4789,4793,4799,4801,4813,4817,4831,4861,4871,4877,4889,4903,4909,4919,4931,4933,4937,4943,4951,4957,4967,4969,4973,4987,4993,4999,5003,5009,5011,5021,5023,5039,5051,5059,5077,5081,5087,5099,5101,5107,5113,5119,5147,5153,5167,5171,5179,5189,5197,5209,5227,5231,5233,5237,5261,5273,5279,5281,5297,5303,5309,5323,5333,5347,5351,5381,5387,5393,5399,5407,5413,5417,5419,5431,5437,5441,5443,5449,5471,5477,5479,5483,5501,5503,5507,5519,5521,5527,5531,5557,5563,5569,5573,5581,5591,5623,5639,5641,5647,5651,5653,5657,5659,5669,5683,5689,5693,5701,5711,5717,5737,5741,5743,5749,5779,5783,5791,5801,5807,5813,5821,5827,5839,5843,5849,5851,5857,5861,5867,5869,5879,5881,5897,5903,5923,5927,5939,5953,5981,5987,6007,6011,6029,6037,6043,6047,6053,6067,6073,6079,6089,6091,6101,6113,6121,6131,6133,6143,6151,6163,6173,6197,6199,6203,6211,6217,6221,6229,6247,6257,6263,6269,6271,6277,6287,6299,6301,6311,6317,6323,6329,6337,6343,6353,6359,6361,6367,6373,6379,6389,6397,6421,6427,6449,6451,6469,6473,6481,6491,6521,6529,6547,6551,6553,6563,6569,6571,6577,6581,6599,6607,6619,6637,6653,6659,6661,6673,6679,6689,6691,6701,6703,6709,6719,6733,6737,6761,6763,6779,6781,6791,6793,6803,6823,6827,6829,6833,6841,6857,6863,6869,6871,6883,6899,6907,6911,6917,6947,6949,6959,6961,6967,6971,6977,6983,6991,6997,7001,7013,7019,7027,7039,7043,7057,7069,7079,7103,7109,7121,7127,7129,7151,7159,7177,7187,7193,7207,7211,7213,7219,7229,7237,7243,7247,7253,7283,7297,7307,7309,7321,7331,7333,7349,7351,7369,7393,7411,7417,7433,7451,7457,7459,7477,7481,7487,7489,7499,7507,7517,7523,7529,7537,7541,7547,7549,7559,7561,7573,7577,7583,7589,7591,7603,7607,7621,7639,7643,7649,7669,7673,7681,7687,7691,7699,7703,7717,7723,7727,7741,7753,7757,7759,7789,7793,7817,7823,7829,7841,7853,7867,7873,7877,7879,7883,7901,7907,7919,7927,7933,7937,7949,7951,7963,7993};
const char g[]="122322325232635222275323525263323226525222C52323263776352653325A:23:22376225253E2275?23=232=327523222223352377323233;5222525322;5635326;222332322;232523252A735223563567;32:>533723632535222;A552723;2352327223262:262==33522=33263732236325>22;22523C3235;35732232;322233333222765:26;653522>:2632232523222523535227252325727532:233G7552223272237C25232273=2253523;63526522523A225262277352333257225C22275333263332623225222;275352552=223:A>22523;62623677335772;235:662333262:623352;F253352537232222725A22722322335235?222=5225227327357252233352252=;2=23232326232522233:53;222<5=225235;63223322227523533:2222>2333E32353222723526;35;52223533?33;2562A5C3622377233;;2336=6237625;225323233;22235262C32562227A27:32377352523;32373533353277232232=;5:22=26;57>3253232;22C252:22763526262327352;O3525273232255522:A3723725533223225325352;272:7223:33=C3222263332372672A:5335>=3222265732252;2332227:23223F352322272227=5235653222325275235773:23325222252252672626752532322657222237222==2352625272323A62352357:2323352<2352322273232655";

离散对数

定义

设 $g$ 是 $m$ 的原根，若 $g^r \equiv a \pmod m$，则称 $r$ 是以 $g$ 为底的 $a$ 对模 $m$ 的一个指标，记为 $\operatorname{ind}(a)$。

性质

性质 1

$a \equiv b \pmod m \Leftrightarrow \operatorname{ind}(a) \equiv \operatorname{ind}(b) \pmod {\varphi(m)}$

性质 2

$\operatorname{ind}(a \times b) \equiv \operatorname{ind}(a)+\operatorname{ind}(b) \pmod {\varphi(m)}$

性质 3

$\operatorname{ind}(a^n) \equiv n \times \operatorname{ind}(a) \pmod {\varphi(m)}$

指标的计算：BSGS 算法

大步小步算法（英语：baby-step giant-step）是丹尼尔·尚克斯发明的一种中途相遇算法，用于计算离散对数。

求同余方程的最小非负整数解：$a^x \equiv b \pmod p$，$(a,p)=1$。

根据欧拉定理 $a^{\varphi(p)} \equiv 1 \pmod p$，可知 $a^x \equiv a^{x \bmod \varphi(p)} \Rightarrow x<\varphi(p)$，枚举的时间复杂度为 $O(p)$，太慢了！

考虑分块，每块大小为 $m$，令 $x=m \times i-j$（$i,j \in \mathbb{N}$，$0 \le j \le m-1$），则有：

$$a^{m \times i-j} \equiv b \pmod p$$

$$(a^m)^i \equiv a^jb \pmod p$$

事先计算 $a^jb$ 并存入哈希表，然后枚举 $i$ 进行匹配，时间复杂度为 $O(m+\dfrac{p}{m})$，$m=\sqrt p$ 时取到最优值 $O(\sqrt p)$。

Luogu P3846：提交记录备份

扩展 BSGS 算法

对于 $\gcd(a,p) \ne 1$ 的情况，$a$ 没有逆元。

设 $\gcd(a,p)=d$，根据同余性质，若 $a \times c \equiv b \times c \pmod p$，$\gcd(c,p)=d$，则 $a \equiv b \pmod {\dfrac{p}{d}}$。

$$\dfrac{a^x}{d} \equiv a^{x-1} \times \dfrac{a}{d} \equiv \dfrac{b}{d} \pmod {\dfrac{p}{d}}$$

$$a^{x-k} \times \dfrac{a^k}{\prod\limits_{i=1}^kd_i} \equiv \dfrac{b}{\prod\limits_{i=1}^kd_i} \pmod {\dfrac{p}{\prod\limits_{i=1}^kd_i}}$$

可以不断提取一个 $a$，最后使得 $\gcd(a,p)=1$，记录一下提取了多少个 $a$，加回到答案即可。

过程中如果 $b$ 不能整除 $d$，则无解；如果已经找到解，则判掉。

Luogu P4195：提交记录备份

底数的计算：第二类指数同余方程

求同余方程的解：$x^k \equiv b \pmod p$，$p$ 为素数。

假设 $g$ 是 $p$ 的一个原根，用 BSGS 解同余方程 $g^m \equiv b \pmod p$。

假设 $x \equiv g^y$，则 $g^ky \equiv g^m \pmod p$。

得到 $g^{ky-m} \equiv 1 \pmod p$。

根据原根的性质，$ky-m \equiv 0 \pmod {\varphi(p)}$。

$\varphi(p)=p-1$，然后就可以用扩展欧几里得算法求解了。

例题

名称	编号	备注	题解
Matrix	BZOJ 4128	BSGS + 矩阵 + hash	提交记录备份
随机数生成器	SDOI2013R1D1T1	用矩阵乘法表示数列的递推，BSGS + 矩阵 + hash	提交记录备份
多少个 1？	Luogu P4884
Lunar New Year and a Recursive Sequence	CF1106F