数学基础
绝顶我为峰
2021-06-15 20:39:14
# 数学基础
## 1.基本定理
- **定理1：若 $p\in prime,p\nmid a$，则 $p\mid ab$ 的充要条件是 $p\mid b$。**
更一般地，若 $\gcd(p,a)=1$，则 $p\mid ab$ 的充要条件是 $p\mid b$。
证明：显然。
- **定理2（裴蜀定理）：$ax+by=n$ 有整数解的充要条件是 $\gcd(a,b)\mid n$。**
证明：令 $\gcd(a,b)=d$。
必要性：假设有整数解，显然 $d\mid ax,d\mid by$，因此有 $d\mid n$。
充分性：两边同时除以 $d$，得 $\frac a d x+\frac b d y=\frac n d$。显然有 $\gcd(\frac a d,\frac b d)=1$，根据欧几里得算法，此时一定有 $x,y$ 使得 $\frac a d x+\frac b d y=1$，再放缩一定可以找到合法解。
得证。
例题：[【模板】裴蜀定理](https://www.luogu.com.cn/problem/P4549)
- **定理3：若 $a,b>0,\gcd(a,b)=1$，那么所有大于 $ab-a-b$ 的数都可以写成 $ax+by(x,y\geq0)$ 的形式，但 $ab-a-b$ 不能。**
证明：我们要证明 $ax+by=ab-a-b$ 无整数解，而 $ax+by=ab-a-b+k(k>0)$ 均有解。
$ax+by=ab-a-b$
$a(x+1)+b(y+1)=ab$
有 $a\mid y+1$
则 $y+1\geq a,b(y+1)\geq ab$
因为 $a(x+1)\geq 1$
所以 $a(x+1)+b(y+1)\geq ab+1> ab$
所以无解。
$ax+by=ab-a-b+k$
$a(x+1)+b(y+1)=ab+k$
令 $x'=x+1,y'=y+1$
由定理2得该不定方程一定有整数解，假设存在一组解 $x'=x_0,y'=y_0$
那么一组解可以写成 $x'=x_0-bt,y'=y_0+at$
显然可以钦定一个 $t$ 使得 $1\leq x'\leq b$，那么 $0\leq x\leq b-1$
此时 $a\leq ax'\leq ab$，则 $by'$ 是正数，所以 $y'\geq 1$，即 $y\geq 0$。所以一定存在合法解。
得证。
例题：[[NOIP2017 提高组] 小凯的疑惑](https://www.luogu.com.cn/problem/P3951)
完全一致。
## 2.同余
### 运算
加减：直接算。
乘：直接乘，但是可能会导致同余弱化。
除：不能直接除，但如果 $ka\equiv kb(mod\ m),\gcd(k,m)=1$，那么 $a\equiv b(mod\ m)$
### 完系与缩系
完系：$m$ 个剩余类每个取一个代表元，$m$ 的一个完系是 $0\sim m-1$。
缩系（简化剩余系）：与 $m$ 互质的等价类中取一个代表元，如 $6$ 的一个缩系是 $1,5$， $7$ 的一个缩系是 $1,2,3,4,5,6$。
### 欧拉函数与欧拉定理
欧拉函数：定义 $\varphi(m)$ 为模 $m$ 意义下缩系大小，显然有 $\varphi(m)=m-1(m\in prime)$。
欧拉函数求法：若 $m=\prod_{i=1}^na_i^{p_i}$，则 $\varphi(m)=m\prod_{i=1}^n1-\frac 1 {p_i}=\prod_{i=1}^n(p_i-1)p_i^{a_i-1}$。
**定理：$\sum_{d\mid m}\varphi(d)=m$**
**引理：若 $a_1,a_2,\dots,a_{\varphi(m)}$ 是缩系且 $\gcd(k,m)=1$，那么 $ka_1,ka_2,\dots ,ka_{\varphi(m)}$ 也是缩系。**
证明：假设变换后不是缩系，那么 $\exists 1\leq i<j\leq \varphi(m),ka_i\equiv ka_j(mod\ m)$
因为 $\gcd(k,m)=1$，所以 $a_i\equiv a_j(mod\ m)$。根据缩系定义，这不可能出现，所以矛盾。
得证。
**欧拉定理：若 $\gcd(k,m)=1$，则 $k^{\varphi(m)}\equiv 1(mod\ m)$。**
证明：设模 $m$ 意义下一个缩系为 $a_1,a_2,\dots ,a_{\varphi(m)}$，那么 $ka_1,ka_2,\dots,ka_{\varphi(m)}$ 也是缩系。
由于缩系中每个元素模 $m$ 后分别对应一个与 $m$ 互质的剩余类，而互质剩余类不会改变，所以对两个缩系做连乘，有 $k^{\varphi(m)}\prod_{i=1}^{\varphi(m)}a_i\equiv \prod_{i=1}^{\varphi(m)}a_i(mod\ m)$。
根据定义，显然 $\gcd(\prod_{i=1}^{\varphi(m)}a_i,m)=1$，由同余除法性质可得 $k^{\varphi(m)}\equiv 1(mod\ m)$。
得证。
**推论：对于任意 $k,m$，有 $k^m\equiv k^{m-\varphi(m)}(mod\ m)$。**
### 费马小定理
**费马小定理：若 $p\in prime$，则 $a^{p-1}\equiv 1(mod\ p)$。**
证明：$p\in prime$，则 $\varphi(p)=p-1$，代入欧拉定理得证。
这个定理最常用来求逆元，因为模数一般是质数，那么 $a^{p-2}·a\equiv 1(mod\ p)$，因此 $a^{p-2}$ 就是$a$ 在模 $p$ 意义下的逆元。
### 阶
高次同余方程的阶：最小的正整数 $d$ 使得 $a^d\equiv 1(mod\ m)$，则 $d$ 为 $a$ 对 $m$ 的阶。由欧拉定理易得阶的存在性。
**定理：若 $a^x\equiv 1(mod\ m)$，则 $d\mid x$。**
证明：显然 $a^{x\%d}\equiv 1(mod\ m)$，若 $x\%d$ 不为 $0$ 则违反了 $d$ 的最小性，矛盾。
得证。
### 原根和指数
原根：若 $x$ 对 $m$ 的阶为 $\varphi(m)$，则称 $x$ 为 $m$ 的原根。
**性质：对于任意一个原根 $x$，$x,x^2,x^3,\dots ,x^{\varphi(m)}$ 是模 $m$ 意义下的一个缩系。**
证明：假设不是缩系，因为 $\gcd(x,m)=1$，所以所有数都是缩系中的数，这样如果不是缩系则 $\exists 1\leq i<j\leq \varphi(m),x^i\equiv x^j(mod\ m)$。
两边做除法得 $x^{j-i}\equiv 1(mod\ m)$。
因为 $j-i<\varphi(m)$，矛盾。
得证。
**定理：$1,2,4,p^k,2p^k(p\in \complement_{prime}{\{2\}},k\in \mathbb{N_+})$ 是所有有原根的数。**
~~证明：不会。~~
由这个定理可以得到素数都有原根。
原根的求法：记最小的原根为 $g$，大约不超过 $O(n^{\frac14})$，暴力找出来，则所有 $g^k(\gcd(k,\varphi(m)=1)$ 都是原根。
通过这种求法容易得到原根共有 $\varphi(\varphi(m))$ 个。
指数：若 $p\in prime$，$a$ 是 $p$ 的原根且 $a^k\equiv b(mod\ m)(k\leq m-1)$，则称 $k$ 为 $b$ 的指数，记作 $\mathrm{ind}_ab$。通过指数可以把模意义乘法变成指数加法。
### 一次同余方程
求 $ax+b\equiv 0(mod\ m)$ 的正整数解。
这东西其实就是 $ax+b=my$，转换成上面的裴蜀定理，不再赘述。
### 中国剩余定理
**$m=\gcd(m_1,m_2)$，则方程组 $x\equiv a_1(mod\ m_1)$ 和 $x\equiv a_2(mod\ m_2)$ 有解的充要条件是 $m\mid a_1-a_2$，且 $x$ 模 $m$ 有唯一解。**
显然当 $\gcd(m_1,m_2)=1$ 时方程组恒有解。
继续推广，得到对于一组 $m_1,m_2,\dots,m_n$，若 $\forall 1\leq i<j\leq n,\gcd(m_i,m_j)=1$，那么方程组 $x\equiv a_i(mod\ m_i)(i\in[1,n]\cup\mathbb{N_+})$ 在模 $\prod_{i=1}^nm_i$ 意义下有唯一解。
我们考虑求出这个解。令 $M_i=\frac{\prod_{j=1}^nm_j}{m_i}$，$b_i$ 满足 $b_iM_i\equiv 1(mod\ m_i)$，则解为 $\sum_{i=1}^na_ib_iM_i$。正确性显然，分别考虑对于模 $m_1$ 到 $m_n$ 的余数即可。
## 3.二次同余方程
### 第一型佩尔方程
形如 $x^2-Dy^2=1(x,y,D\in\mathbb{N_+})$ 的方程称为第一型佩尔方程。
**定理1：第一型佩尔方程在 $\sqrt D\in\mathbb{N_+}$ 时无正整数解，否则有无穷多组正整数解。**
证明：显然 $x^2$ 是完全平方数，$Dy^2=x^2-1$ 不是完全平方数，而 $y^2$ 是完全平方数，因此若有正整数解 $D$ 一定不能是完全平方数。
**定理2：若最小解为 $x_0,y_0$，那么任意一个解 $x_n,y_n$ 满足 $x_n+\sqrt Dy_n=(x_0+\sqrt Dy_0)^{n+1}$，由此得到递推式 $x_n+\sqrt Dy_n=(x_{n-1}+\sqrt Dy_{n-1})(x_0+\sqrt Dy_0)$。**
~~证明：还是不会。~~
实际应用中 $D$ 一般不会太大，可以先暴力算出 $x_0,y_0$，然后利用**递推式**直接求解（直接用通项会掉精度）。
例如 $x^2-2y^2=1$，很容易算出 $x_0=3,y_0=2$，那么 $x_1+\sqrt2y_1=(3+2\sqrt2)^2=17+12\sqrt2$，因此 $x_1=17,y_1=12$。
### 第二型佩尔方程
形如 $x^2-Dy^2=-1(x,y,D\in\mathbb{N_+})$ 的方程称为第二型佩尔方程。
同样的，在 $\sqrt D\in\mathbb{N_+}$ 时无解，否则有无穷多解。
找到最小解 $x_0,y_0$，一组解 $x_n,y_n$ 满足 $x_n+\sqrt Dy_n=(x_0+\sqrt Dy_0)^{2n+1}$，递推式 $x_n+\sqrt Dy_n=(x_{n-1}+\sqrt Dy_{n-1})(x_0+\sqrt Dy_0)^2$。
例题：给定 $T$，求使 $n(n+1)=2m(m+1)$ 有正整数解的大于 $T$ 的最小 $n$。
$n^2+n=2m^2+2m$
$4n^2+4n=8m^2+8m$
$(2n+1)^2=2(2m+1)^2-1$
$(2n+1)^2-2(2m+1)^2=-1$
令 $x=2n+1,y=2m+1$
$x^2-2y^2=-1$
手算 $x_0,y_0$，暴力递推，因为增长是指数的所以可以过，也可以矩阵快速幂倍增。
### 勾股方程
$x^2+y^2=z^2$ 叫做勾股方程。
勾股方程的通解是 $x=2kuv,y=k(u^2-v^2),z=k(u^2+v^2)$，其中 $u,v,k\in\mathbb{N_+},u>v,\gcd(u,v)=1$。
证明：显然 $k$ 可以最后放缩，我们只要证明对于 $\gcd(x,y,z)=1$ 时，满足 $x=2uv,y=u^2-v^2,z=u^2+v^2$
根据加法的奇偶性，$x,y,z$ 必然是两奇一偶。
同时 $z$ 一定是奇数，因为如果 $z$ 是偶数，那么 $z^2\equiv 0(mod\ 4)$，而左边两奇数 $x^2\equiv y^2\equiv 1(mod\ 4)$，$x^2+y^2\equiv 2(mod\ 4)$，两边不可能相等。
$x,y$ 等价，不妨令 $y$ 是偶数。
移项，得到 $x^2=(z+y)(z-y)$，显然 $\gcd(y,z)=1$，否则 $x,y,z$ 不互质。那么 $\gcd(z+y,z)=1$。因为 $z+y$ 是奇数，所以 $\gcd(z+y,2z)=1$。辗转相除一次，得到 $\gcd(z+y,z-y)=1$。
两个互质的数乘起来是完全平方数，那么必须分别是完全平方数，所以有 $z+y=u^2,z-y=v^2$，解得 $x=uv,y=\frac{u^2-v^2}2,z=\frac{u^2+v^2}2$。
得证。
这样构造出的勾股方程的解满足 $\gcd(x,y,z)=k$。
勾股方程通解可以优化枚举勾股数的效率。
## 4.排列组合
### 勒让德定理
$p\in prime$，则 $n!$ 质因数分解中 $p$ 的次数是 $\sum_{i=1}\lfloor\frac{n}{p^i}\rfloor=\frac{n-S(n)}{p-1}$，$S(n)$ 表示 $p$ 进制下 $n$ 的数位和。
推论：$\dbinom {n+m}m$ 中 $p$ 的幂次等于 $n+m$ 在 $p$ 进制下进位次数。
### 卢卡斯定理
若 $p$ 进制下 $n$ 表示为 $(a_0a_1\dots a_m)$，$k$ 表示为 $(b_0b_1\dots b_m)$（允许前导 0），那么 $\dbinom n k\equiv\prod_{i=0}^m\dbinom{a_i}{b_i}(mod\ p)$
这个定理用于计算大组合数取模。
例题：[【模板】卢卡斯定理](https://www.luogu.com.cn/problem/P3807)
直接应用结论即可。
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
int t,n,m,p,fac[200001],inv[200001];
inline int pw(int a,int b)
{
int res=1;
while(b)
{
if(b&1)
res=res*a%p;
b>>=1;
a=a*a%p;
}
return res;
}
inline int c(int x,int y)
{
return fac[x]*inv[y]%p*inv[x-y]%p;
}
int lucas(int x,int y)
{
if(!x||!y)
return 1;
return c(x%p,y%p)*lucas(x/p,y/p)%p;
}
signed main()
{
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld%lld",&n,&m,&p);
int tmp=n;
n=n+m;
m=tmp;
fac[0]=inv[0]=1;
for(register int i=1;i<=n;++i)
{
fac[i]=fac[i-1]*i%p;
inv[i]=pw(fac[i],p-2);
}
printf("%lld\n",lucas(n,m));
}
return 0;
}
```
## 5. 莫比乌斯函数
定义：
$$\mu(n)=\left\{
\begin{aligned}
1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (n=1) \\
(-1)^k\ \ \ \ (n=\prod_{i=1}^kp_i(p_i\in prime))\\
0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (\mathrm{otherwise}) \\
\end{aligned}
\right.
$$
莫比乌斯反演：若 $f(n)=\sum_{d\mid n}g(d)$，则 $g(n)=\sum_{d\mid n}\mu(d)f(\frac n d)$。
这个反演也可以理解成卷积：若 $g*1=f$，那么 $f*\mu=g$。
性质：$\sum_{d\mid n}\mu(d)=[n=1]$
证明：$n=1$ 显然成立。
设 $n=\prod_{i=1}^mp_i^{a_i}(p_i\in prime)$，那么所有 $\mu(d)$ 非零的位置必然是在 $p_1,p_2,\dots,p_m$ 中选择若干个乘起来得到的，共有 $2^m$ 个位置。
只考虑 $p_1$，依据是否选择 $p_1$ 可以将 $2^m$ 个数分成两组，不妨设含 $p_1$ 的一组为 $A$，不含的一组为 $B$，显然每组有 $2^{m-1}$ 个数。
有一个显然的结论：$\forall d\in B,p_1d\in A$。这是因为 $A,B$ 中的元素是一一对应的。那么在 $B$ 中 $\mu(d)=-1$ 的 $d$，$\mu(p_1d)=1$，因为多了一个素因子 $p_1$，反过来也同理，由此我们得到了 $\sum_{d\in A}[\mu(d)=1]=\sum_{d\in B}[\mu(d)=-1]$ 和 $\sum_{d\in A}[\mu(d)=-1]=\sum_{d\in B}[\mu(d)=1]$，所以在 $2^m$ 个数中 $\mu(d)=1$ 和 $\mu(d)=-1$ 的个数是相等的，因此相加为零。
得证。
例题：求 $\phi(i)=\sum_{i=1}^n\varphi(i)$。
这玩意可以直接杜教筛 $\phi(i)$，也可以筛 $\mu$ 的前缀和+数论分块。
杜教筛下面会写，先拿它当一个莫反练手题。
上文提到 $\sum_{d\mid n}\varphi(d)=n$，刚好是莫反的形式（$f(n)=\mathrm{id},g(n)=\varphi(n)$），直接莫反一下代入上式。
$\phi(i)=\sum_{i=1}^n\sum_{d\mid i}\mu(d)\frac i d$
接下来套路地先枚举 $d$。
$\phi(i)=\sum_{d=1}^n\mu(d)\sum_{i=1}^{\lfloor\frac n d\rfloor}i$
前半部分杜教筛，后半部分数论分块。
## 6.杜教筛
杜教筛可以在低于线性的时间内求**积性函数**的前缀和。他的思想是暴力筛出较小的一些函数值，在较大的定义域上递归求解。
假设我们要求 $S(n)=\sum_{i=1}^nf(i)$，现在我们假设通过一种玄妙的手段找来另一个函数 $g(i)$，现在把他俩卷起来得到 $h(i)$ ，对 $h$ 求一个前缀和：
$\sum_{i=1}^nh(i)=\sum_{i=1}^n\sum_{d|i}g(d)f(\frac i d)$
$=\sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor\frac n d\rfloor}f(i)=\sum_{d=1}^ng(d)S(\lfloor\frac n d\rfloor)$
我们想要 $S(n)$，我们发现 $h(i)$ 的前缀和大致相当于 $g*S$（虽然不完全是），所以在前缀和里面会有一项 $g(1)S(n)$，$g(1)$ 显然是易得的，于是我们决定看看这个怎么算。
利用前缀和思想可以得到:
$g(1)S(n)=\sum_{i=1}^ng(i)S(\lfloor\frac n i\rfloor)-\sum_{i=2}^ng(i)S(\lfloor\frac n i\rfloor)$
$=\sum_{i=1}^nh(i)-\sum_{i=2}^ng(i)S(\lfloor\frac n i\rfloor)$
我会递归！只要快速计算 $h(i)$ 和 $g(i)$ 的前缀和就好了！问题圆满解决……了吗？
我们似乎还不知道 $g(i)$ 是什么。事实上这在不同的题目里是不同的，但选取 $g(i)$ 的原则是一致的：需要使得 $h(i)$ 和 $g(i)$ 的前缀和均易于计算。
下面有几个例子帮助理解 $g(i)$ 的选取。
- 求 $\sum_{i=1}^n\mu(i)$。
根据 $\mu*1=\epsilon$ 这一经典的性质，不难想到 $g$ 应该取 $1$，此时 $h=\epsilon$，而这俩东西的前缀和一个都巨大简单，然后就很快乐的做完了。
- 求 $\phi(i)$
根据 $\varphi(i)*1=\mathrm{id}$ 这一性质，不难想到 $g=1$，此时 $h=\mathrm{id}$，这俩东西前缀和也巨大简单，于是也做完了。
朴素杜教筛复杂度 $O(n^{\frac 3 4})$，做一些优化可以达到 $O(n^{\frac 2 3})$。
例题：[【模板】杜教筛（Sum）](https://www.luogu.com.cn/problem/P4213)，就是上面两个例子合起来。
```cpp
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
#define int long long
int t,n,phi[5000001],mu[5000001],p[5000001],cnt;
bool vis[5000001];
map<int,int> sphi,smu;
inline void init()
{
mu[1]=phi[1]=1;
for(register int i=2;i<=5000000;++i)
{
if(!vis[i])
{
p[++cnt]=i;
phi[i]=i-1;
mu[i]=-1;
}
for(register int j=1;j<=cnt&&p[j]*i<=5000000;++j)
{
vis[p[j]*i]=1;
if(i%p[j]==0)
{
phi[p[j]*i]=p[j]*phi[i];
break;
}
else
{
phi[p[j]*i]=(p[j]-1)*phi[i];
mu[p[j]*i]=-mu[i];
}
}
}
for(register int i=2;i<=5000000;++i)
{
phi[i]+=phi[i-1];
mu[i]+=mu[i-1];
}
}
int getphi(int n)
{
if(n<=5000000)
return phi[n];
if(sphi[n])
return sphi[n];
int res=n*(n+1)/2;
for(register int i=2,j;i<=n;i=j+1)
{
j=n/(n/i);
res-=(j-i+1)*getphi(n/i);
}
return sphi[n]=res;
}
int getmu(int n)
{
if(n<=5000000)
return mu[n];
if(smu[n])
return smu[n];
int res=1;
for(register int i=2,j;i<=n;i=j+1)
{
j=n/(n/i);
res-=(j-i+1)*getmu(n/i);
}
return smu[n]=res;
}
signed main()
{
scanf("%lld",&t);
init();
while(t--)
{
scanf("%lld",&n);
printf("%lld %lld\n",getphi(n),getmu(n));
}
return 0;
}
```
## 7.二次剩余
### 定义及求解
定义：$m>1$，若 $\gcd(n,m)=1$ 且 $x^2\equiv n(mod\ m)$ 有解，那么称 $n$ 是 $m$ 的二次剩余。
勒让德符号：若$n\equiv 0(mod\ m)$，那么 $(\frac n m)=0$，否则，若 $n$ 是 $m$ 的二次剩余，那么 $(\frac n m)=1$，否则 $(\frac n m)=-1$。
**定理：$p\in prime$，则 $p$ 的缩系中恰好有一半数是二次剩余，另一半不是。**
证明：素数，则小于 $p$ 的正整数都在缩系里。首先证明存在 $\frac{p-1}2$ 个二次剩余。假设他们分别为 $1^2\%p,2^2\%p,\dots,(\frac{p-1}2)^2\%p$。他们显然都是二次剩余，我们只要证明他们两两互不相同即可。
假设 $\exists1\leq i<j\leq\frac{p-1}2,i^2\equiv j^2(mod\ p)$，那么有 $(j+i)(j-i)\equiv 0(mod\ p)$。显然 $j-i<j+i<p$，矛盾。
因此存在 $\frac{p-1}2$ 个二次剩余。
加下来证明只有 $\frac{p-1}2$ 个二次剩余。我们考虑刚才没有选中的 $(\frac{p+1}2)^2\%p,(\frac{p+3}2)^2\%p,\dots,(p-1)^2\%p$，容易发现 $1^2\equiv(p-1)^2(mod\ p),2^2\equiv(p-2)^2(mod\ p)$，以此类推，两组二次剩余一一对应，因此二次剩余恰有 $\frac{p-1}2=\frac{\varphi(p)}2$ 个。
得证。
**欧拉判别法：若 $p\in\complement_{prime}{\{2\}}$，则 $n^{\frac{p-1}2}\equiv(\frac n p)(mod\ p)$**。
证明：如果 $n$ 是二次剩余，那么令 $n=x^2\%p$，那么左边变成 $x^{p-1}\%p$，由费马小定理得到左边=右边=$1$，成立。
如果 $n$ 不是二次剩余，根据拉格朗日定理（$n$ 次同余方程最多有 $n$ 个解），$n^{\frac{p-1}2}\equiv1(mod\ p)$ 这一同余方程至多有 $\frac{p-1}2$ 个解，而二次剩余恰好有 $\frac{p-1}2$ 个，所以每一个解对应一个二次剩余，不是二次剩余左边一定不是 $1$。但根据费马小定理，我们知道 $(n^{\frac{p-1}2})^2=n^{p-1}\equiv1(mod\ p)$，那么 $n^{\frac{p-1}2}$ 就只能是 $-1$ 了。
得证。
由欧拉判别法还可以得到勒让德符号是一个积性函数，因为 $(\frac n p)(\frac m p)\equiv n^{\frac{p-1}2}m^{\frac{p-1}2}\equiv (nm)^{\frac{p-1}2}\equiv(\frac{nm}p)(mod\ p)$。
还可以简单地得到两个二次剩余或两个非二次剩余乘积是二次剩余，一个二次剩余和一个非二次剩余的乘积是非二次剩余。
**以下是手算二次剩余的方法，偏 $MO$，不感兴趣的可以略过。**
根据勒让德符号的积性，算 $(\frac n p)$ 时可以直接把 $n$ 质因数分解，然后直接求素数是否为二次剩余即可。
**定理：$(\frac 2 p)=(-1)^{\frac{p^2-1} 8}$。**
**$Gauss$ 二次互反律：$p,q\in\complement_{prime}{\{2\}},p\not=q$，则 $(\frac p q)(\frac q p)=(-1)^{\frac{(p-1)(q-1)}4}$。**
通过上述两个定理可以快速手算 $(\frac n m)$
**下面是 $OI$ 中计算二次剩余的方法。**
定理：对于二次剩余方程 $x^2\equiv n(mod\ p)$，$p$ 是奇素数，找到一个 $a$ 使得 $(\frac{a^2-n} p)=-1$，那么 $x=(a+\sqrt{a^2-n})^{\frac{p+1}2}$ 是原方程的解。其中对非二次剩余的部分开根类似于复数，有一套新的运算法则，可以做模板题了解一下。
证明：可以去看模板题题解，我~~因为懒~~就不写了。
例题：[【模板】二次剩余](https://www.luogu.com.cn/problem/P5491)
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<ctime>
using namespace std;
#define int long long
int inv,t,n,mod;
struct cp
{
int x,y;
cp(int x_,int y_):
x(x_),y(y_){}
cp operator *(const cp &other) const
{
return cp((x*other.x%mod+inv*y%mod*other.y%mod)%mod,(x*other.y%mod+y*other.x%mod)%mod);
}
};
inline cp pw(cp a,int b)
{
cp res=cp(1,0);
while(b)
{
if(b&1)
res=res*a;
b>>=1;
a=a*a;
}
return res;
}
signed main()
{
srand(time(NULL));
scanf("%lld",&t);
while(t--)
{
inv=0;
scanf("%lld%lld",&n,&mod);
if(!n)
{
puts("0");
continue;
}
if(pw(cp(n,0),(mod-1)>>1).x==mod-1)
{
puts("Hola!");
continue;
}
int a=rand()%mod;
while(!a||pw(cp((a*a%mod-n+mod)%mod,0),(mod-1)>>1).x==1)
a=rand()%mod;
inv=(a*a%mod-n+mod)%mod;
int ans=pw(cp(a,1),(mod+1)>>1).x;
if(mod-ans<ans)
ans=mod-ans;
printf("%lld %lld\n",ans,mod-ans);
}
return 0;
}
```
### 二次同余式
**定理：若 $L>0,p>2,p\in prime,p\nmid n$，那么 $x^2\equiv n(mod\ p^L)$ 有 $1+(\frac n p)$ 个解。**
推广：如果 $p=2$，$L=1$ 时有一个解；$L=2$ 时若 $n\equiv 0(mod\ p^L)$ 或 $n\equiv 1(mod\ p^L)$ 时有两个解，否则无解；$L>2$ 时若 $n\equiv 1(mod\ 8)$ 有四个解，否则无解。
~~证明：依然是不会。~~
例题：求 $x^2\equiv1(mod\ n)$ 的解的个数。
设 $n=\prod_{i=1}^mp_i^{a_i}$，然后拆了用 $CRT$ 合并。
那么会得到 $m$ 个方程 $x^2\equiv 1(mod\ p_i^{a_i})$，如果 $p_i$ 有 $2$ 先特判掉，然后根据上面这个定理，每个方程的解的个数和 $x^2\equiv 1(mod\ p_i)$ 是一样的（因为 $L$ 并不影响）。于是搞出来直接乘法原理即可。
### 高次同余式
**定理：$x^k\equiv 1(mod\ p)(p\in prime)$ 有 $\gcd(k,p-1)$ 个解。**
将这个定理推广，可得 $x^k\equiv n(mod\ p)(p\in prime)$ 在 $p\nmid n$ 时无解或有 $\gcd(k,p-1)$ 个解。
## 8.升幂问题
**升幂定理：若 $p$ 是奇素数，$p\nmid ab,p\mid a-b$，那么 $a^n-b^n$ 中 $p$ 的幂次等于 $a-b$ 中 $p$ 的幂次与 $n$ 中 $p$ 的幂次之和。**