模逆元

参考资料

如果线性同余方程 $ax\equiv 1\pmod p$ ，则 $x$ 称为 $a$ 在模 $p$ 意义下的逆元（Inverse），记为 $x=a^{-1}$ 。

根据费马小定理（Fermat's Little Theorem）：

aa^{p-2}=a^{p-1}\equiv 1\pmod p

x=a^{p-2}

快速幂：Pow(a,mod-2)。

如果 $ax\equiv 1\pmod p$ ，说明存在整数 $x,y$ 满足 $ax+py=1$ 。

扩展欧几里得算法：exgcd(a,mod)。

\begin{aligned} & p\bmod i=p-\left\lfloor\frac{p}{i}\right\rfloor\cdot i \\ & p\bmod i\equiv-\left\lfloor\frac{p}{i}\right\rfloor\cdot i\pmod p \\ & i^{-1}\cdot(p\bmod i)\equiv-\left\lfloor\frac{p}{i}\right\rfloor\pmod p \\ & i^{-1}\equiv-\left\lfloor\frac{p}{i}\right\rfloor(p\bmod i)^{-1}\pmod p \end{aligned}

98 Bcpp
ll inv[N];
void init()
{
	for(int i=1;i<N;i++)
	{
		inv[i]=i==1?1:(mod-mod/i)*inv[mod%i]%mod;
	}
}

给定两个整数 $n,p$ ，求 $1\sim n$ 中所有整数在模 $p$ 意义下的乘法逆元。（ $n\le3\times10^6,n<p<20000528$ ）

保证 $p$ 是质数。

给定 $n$ 个正整数 $a_i$ ，求它们在模 $p$ 意义下的乘法逆元。

由于输出太多不好，所以将会给定常数 $k$ ，你要输出的答案为：

\sum\limits_{i=1}^n\frac{k^i}{a_i}

答案对 $p$ 取模。

给出一个有理数 $c=\frac{a}{b}$ ，求 $c \bmod 19260817$ 的值。

这个值被定义为 $bx\equiv a\pmod{19260817}$ 的解。

求同余方程 $ax\equiv1\pmod b$ 的最小正整数解。（ $a,b\le2\times10^9$ ）