【数论】原根、指标、同余方程
原根
在(a,m)=1时,定义a对模m的指数$\delta m(a)$为使$a^d \equiv 1 \pmod{m}$成立的最小的正整数d
若$\delta m(a)=\varphi(m)$,则称a是模m的原根
模$m$有原根的充要条件是$m = 2 , 4 , p^n , 2p^n$,其中$p$是奇素数,$n$是任意正整数。
原根定理
素数p的原根个数为$\varphi(p-1)$
指标
当确定模p和原根g时,定义a的指标为$I(a)$为使$g^d \equiv a \pmod p$成立的最小的正整数d
指标法则
①$$I(ab) \equiv I(a)+I(b) \pmod {p-1}$$
②$$I(a^k) \equiv kI(a) \pmod {p-1}$$
求原根
从小到大枚举数$g$判断其是不是原根
对于一个待检查的$g$,检查下面式子是否成立
$$g^{(p-1)/a} \equiv 1 \pmod p$$
若成立则g不为原根(其中a为p-1的质因子)
求所有原根
若已求得一个模p意义下的原根g,则所有原根为
$$g^k \quad (gcd(k,p-1)=1)$$
二次剩余
与一个平方数模$p$同余的非零数为模$p$的二次剩余,与任意平方数模$p$都不同余的非零数为模$p$的非二次剩余
对于奇素数p,各有$\frac {p-1}{2}$个二次剩余和非二次剩余
勒让德符号
$$\left(\frac{a}{p}\right) = \begin{cases} +1 \\ -1 \end{cases}$$
二次互反率
设$p,q$为不同的奇素数,则
$$\left(\frac{-1}{p}\right)=\begin{cases} +1 \quad 如果p \equiv 1 \pmod 4 \\ -1 \quad 如果p \equiv 3 \pmod 4\end{cases}$$
$$\left(\frac{2}{p}\right)=\begin{cases} +1 \quad 如果p \equiv 1或7 \pmod 8 \\ -1 \quad 如果p \equiv 3或5 \pmod 8\end{cases}$$
$$\left(\frac{q}{p}\right)=\begin{cases} +\left(\frac{p}{q}\right) \quad 如果p \equiv 1 \pmod 4或q \equiv 1 \pmod 4\\ -\left(\frac{p}{q}\right) \quad 如果p \equiv q \equiv 3 \pmod 4\end{cases}$$
广义二次互反律
设$p,q$为正奇数,则
$$\left(\frac{-1}{b}\right)=\begin{cases} +1 \quad 如果b \equiv 1 \pmod 4 \\ -1 \quad 如果b \equiv 3 \pmod 4\end{cases}$$
$$\left(\frac{2}{b}\right)=\begin{cases} +1 \quad 如果b \equiv 1或7 \pmod 8 \\ -1 \quad 如果b \equiv 3或5 \pmod 8\end{cases}$$
$$\left(\frac{a}{b}\right)=\begin{cases} +\left(\frac{b}{a}\right) \quad 如果a \equiv 1 \pmod 4或b \equiv 1 \pmod 4\\ -\left(\frac{b}{a}\right) \quad 如果a \equiv b \equiv 3 \pmod 4\end{cases}$$
二次剩余求解
求$x^2 \equiv a \pmod p$最小非负整数解,其中p为素数
①
当p为2时,$x=a \mod p$
②
当p为奇素数时
由欧拉准则可知,$a^{(p-1)/2} \equiv \left( \frac{a}{p} \right) \pmod p$
当$a^{(p-1)/2} \equiv -1 \pmod p$时无解;
当$a^{(p-1)/2} \equiv 1 \pmod p$且$p \equiv 3 \pmod 4$时,$x=a^{(n+1)/4}$;
当$a^{(p-1)/2} \equiv 1 \pmod p$且$p \equiv 1 \pmod 4$时:
设$$b^{(p-1)/2} \equiv -1 \pmod p ~,~ i=(n-1)/2 ~,~ k=0$$
所以$$a^ib^k \equiv 1 \pmod p$$
若$i \mod 2=0$,则$i,k$同时取半,此时$a^ib^k \equiv \pm1 \pmod p$
若$a^ib^k \equiv -1 \pmod p$,则$k=k+(n-1)/2$
不断递归下去,直到$i \mod 2=1$
最后$x=a^{(i+1)/2}b^{k/2}$
离散对数(BSGS算法)
解$a^x \equiv b \pmod p$的最小整数解,其中p为素数
解法:BSGS算法
设s是满足$s*s>p$的最小整数
先预处理出$x^i(i \in [0,s-1])$并用Hash表储存
然后枚举$x^{is}(i \in [0,s-1])$,通过乘法逆元求出满足$c*x^{is}\equiv n(mod\;p)$的c,再判断c是否位于Hash表内,从而找到解
map<int,int>mp; inline void BSGS(int a, int b, int p) { mp.clear(); int s=(int)sqrt(p); while (1LL*s*s<=p) s++; int cnt=1; rep(i, 0, s-1) {if (!mp.count(cnt)) mp[cnt]=i; cnt=1LL*cnt*a%p;} int mul=cnt, tmp; cnt=1; rep(i, 0, s-1) { tmp=1LL*b*Pow(cnt,p-2,p)%p; if (mp.count(tmp)) {printf("%lld\n", 1LL*i*s+mp[tmp]); return;} cnt=1LL*cnt*mul%p; if (cnt==0) break; } puts("Orz, I cannot find x!"); }
离散对数(ExBSGS算法)
解$a^x \equiv b \pmod m$的最小整数解
首先在$[0,log(m)]$的范围内暴力枚举x
不妨令$d=gcd(a,m)$,若d=1则直接套用BSGS,若$b \mod d \not= 0$则无解
其余情况我们则将原式两边同除$d$
$$a^x \equiv b \pmod m ~\Rightarrow~ \frac ad*a^{x-1} \equiv \frac bd \pmod {\frac md}$$
继续重复,直到$d=gcd(a,\frac m{d_1d_2...})=1$
此时原式
$$\frac {a^k}{d_1d_2...}*a^{x-k} \equiv \frac {b}{d_1d_2...} \pmod {\frac {m}{d_1d_2...}}$$
$$a^{x-k} \equiv \frac {b}{d_1d_2...}*(\frac {a^k}{d_1d_2...})^{-1} \pmod {\frac {m}{d_1d_2...}}$$
接下来就求逆元完套BSGS
N次剩余求任意解
求$x^k \equiv b \pmod m$任意解,其中$gcd(b,m)=gcd(k,\varphi(m))=1$
设数$u$满足
$$ku \equiv 1 \pmod {\varphi(m)}$$
则解为
$$x=b^u \pmod m$$
证明:
$$\begin{align} x^k &= (b^u)^k \\ &= b^{uk} \\ &= b^{1+\varphi(m)v} \\ &= b \cdot (b^{\varphi(m)})^v \\ & \equiv b \pmod m \end{align}$$
N次剩余求所有解
求$x^k \equiv b \pmod p$所有解
设$g$为原根,令$g^y=x ~,~g^t=b$,则有$$g^{yk} \equiv g^t \pmod p ~\Rightarrow~ yk \equiv t \pmod {p-1}$$
求原根g完,t用离散对数求,y用Exgcd求,x用快速幂求
询问某数是否为两平方数之和
①素数$p$能表示成两平方数之和
条件:
$$p是两平方数之和 \quad \Leftrightarrow \quad p \equiv 1 \pmod 4$$
求具体方案:费马降阶法
②正整数$m$能表示成两平方数之和
将$m$分解成
$$m=p_1p_2...p_rM^2$$
其中$p_1,p_2,...,p_r$是互不相同的素因子
条件:$$p_i=2~或~p_i \equiv 1 \pmod 4 \quad (i \in [1,r])$$
②正整数$m$能表示成$m=a^2+b^2$且$gcd(a,b)=1$
条件:
$$m \mod 2=1 ~且~ p \equiv 1 \pmod 4 ~ (p|m)$$
$$m \mod 2=0 ~且~ m/2 \mod 2=1 ~且~ p \equiv 1 \pmod 4 ~ (p|m/2)$$
③c能表示成$c^2=a^2+b^2$且$gcd(a,b)=1$
条件:
$$p \equiv 1 \pmod 4 ~ (p|c)$$