前言

只知其一，不知其二

例题 POJ 1845 (opens new window)

由于该题的$p=9901$，计算等比数列和时，除数可能为$p$的倍数，此时不可使用逆元计算。

$a/b \% c = a \% (b*c)/b$

前提: $a/b$为整数

证明:

存在整数$k$使得

$\frac{a}{b}\%c=\frac{a}{b}-kc$

因此

$\frac{a}{b}\%c=\frac{a-kbc}{b}$

注意上面的式子用的是等号而非同余

根据上述定理，可以使用以下代码求解本题

ll get_sum(ll p, ll t){ // 求 1, p, p^2 ... p^t 的和
    // qpow(p, t, d) 以为p的t次方对d取余
    ll div = (p-1) * mod;
    ll ans = (qpow(p, t+1, div) - 1 + div) % div;
    ans = ans / (p-1);
    return ans % mod;
}

逆元

若$ax\equiv 1 \pmod{p}$，且$p,a$互质，那么就定义$x$为$a$在模$p$意义下的逆元，记为$a^{-1}$

快速幂求逆元(费马小定理)

若p为素数, a为正整数, 且 $a 、 p$ 互质。则有 $a^{p-1} \equiv 1\pmod p$

因此，$a^{-1}\equiv a^{p-2} \pmod{p}$

线性求逆元

显然$1\equiv 1 \pmod{p}$

对于当前$i$，设$k,r$使得$p=k*i+r,(1\lt r \lt i \lt p)$，即$k=\left\lfloor\frac{p}{i}\right\rfloor, r=p\mod{i}$.

那么$ki+r\equiv 0\pmod{p}$，两边同时乘上$i^{-1}r^{-1}$

得：$kr^{-1}+i^{-1}\equiv 0\pmod{p}$

即：$i^{-1}\equiv-kr^{-1}\equiv -\lfloor\frac{p}{i}\rfloor\ (p\mod i)^{-1}\pmod{p}$

为避免负数，可改写为$i^{-1}\equiv (p-\lfloor\frac{p}{i}\rfloor)(p\mod i)^{-1}\pmod{p}$

inv[1] = 1;
for(int i=2; i<=n; i++){
	inv[i] = (p - p / i)  * inv[p % i] % p;
}

欧拉降幂

$$a^{b}=\left\{\begin{array}{ll}a^{b \% \varphi(p)} & g c d(a, p)=1 \\a^{b} & g c d(a, p) \neq 1, b<\varphi(p) \\a^{b \% \varphi(p)+\varphi(p)} & g c d(a, p) \neq 1, b \geq \varphi(p)\end{array}\right.$$

其中$\varphi(x)$为欧拉函数（小于或等于$x$的正整数中，与$x$互质的数的个数，当$x$为质数，$\varphi(x)=x-1$）

其中第一条为欧拉降幂，剩余两条为广义欧拉降幂