前置知识

基本的取模运算

加法：$(a + b) \% p = ((a\%p)+(b\%p))\%p$

减法：$(a - b) \% p = ((a\%p)-(b\%p))\%p$ ，注意：为防止出现负数，再加$p$，$(a - b) \% p = ((a\%p)-(b\%p)+p)\%p$

乘法：$(a \times b) \% p = ((a\%p)\times(b\%p))\%p$

注意除法取模，需要使用逆元，将除法转换为乘法。

• 请利用带余除法进行证明

---

快速幂

已知 $a,b,p$，求 $a^b \bmod p$。

方法1：分治

由 $b=q *2+b\%2$ 得到$a^b=a^q \times a^q \times a^{b\%2}$，其中 $q=\left \lfloor b/2 \right \rfloor$,即 $a^b=a^{b/2} \times a^{b/2} \times a^{b\%2}$

$a^{b/2}$ 与原问题具有相同结构的子问题，可以递归求解。对应的时间复杂度为 $T(n)=T(n/2)+O(1)$ ,得到 $T(n)=O(\log_2{n})$。

核心代码如下：

int p;
int pw(int a,int b)
{
	if(b==0)return 1;
	int x=pw(a,b/2);
	if(b&1)
		return (((long long)x*x)%p*(long long)a)%p;
	else return (long long)x*x%p;	
}

注意：int 型 乘 int 型会炸 int (溢出)，所以需要类型转换成 long long.

方法2：倍增

举例说明，若 $b=15$,转为二进制可得 $15=(1111)_2$

$a^{15}=a^{1111}=a^8*a^4 *a^2*a^1$ ，发现是若干个 $a$ 翻倍相乘得到。

$a^{13}=a^{1101}=a^8*a^4 *a^1$，当 $b$ 中对应二进制为 $1$,将 $a$ 翻倍的值乘入,否则丢弃。

设变量 $base=a$ ,翻倍一次（倍增）就是 $base=base*base$ ，可以依次得到 $a^1,a^2,a^4,a^8\dots$ ，当 $b$ 中二进制对应位为 $1$ ，乘入结果。

核心代码：

int p;
int pw(int a,int b)
{
	int base=a,ans=1;
	if(b==0)return 1%p;
	while(b)
	{
		if(b&1)ans=(long long)ans*base%p;
		base=(long long)base*base%p;
		b>>=1;
	}
	return ans;
} 

---

逆元

当遇到 $(a/b)\%p$ 的情况，需要将除法转为乘法。

逆元定义：正整数 $b,p$，如果有 $bx ≡ 1\mod p$，则称 $x$ 的最小正整数解为 $b$ 模 $p$ 的逆元。

$(a/b)\%p = a*1/b \%p =a*bx/b \%p =a*x \%p$

逆元求法很多，比如扩展欧几里得、费马小定义、欧拉定理等。当 $p$ 为质数时，费马小定义最为简单，转化为快速幂求解。

费马小定理：如果 $p$ 是一个质数，而整数 $b$ 不是 $p$ 的倍数，则有 $b^{(p-1)}≡1(\mod p)$ 。

由费马小定理，可得 $b \ne 0$ 在模 $p$ 下的逆元, $b*b^{p-2}≡1(\mod p)$ ,$b$ 的逆元为 $x=b^{p-2} \mod p$ 。

当 $p$ 不是质数时,可以利用欧拉定理求逆元：

如果 $gcd(a,p)=1$, 则 $a^{\varphi(p)} ≡ 1 \mod p$.

即求出 $\varphi(p)$ 后求出逆元。(可以看到费马小定理是欧拉定理的特殊情况)