中国剩余定理（$\textbf{CRT}$）解决问题类型例题：洛谷 P1495 【模板】中国剩余定理（CRT）（本题需要使用 快速乘，否则超出 unsigned long long 的存储范围）。 给定 $n$ 个两两互质的正整数，构成序列 $\{...

裴蜀定理形式 若 $a,b\in\mathbb{Z}$，那么对于 $\forall x,y\in\mathbb{Z}$，$\gcd(a,b)\mid a\times x+b\times y$。 此外，一定 $\exist\,x,y \in \math...

取模定义对于 $a,b\in\mathbb{Z}$，满足 $b>0$，则存在唯一的整数 $q,r$，满足 $a=b\times q+r\,(0\le r

逆元定义如果 $ax\equiv 1\pmod p$，则称 $x$ 为 $a$ 在模 $p$​ 意义下的乘法逆元。 逆元存在当且仅当 $a\perp p$，即 $\gcd(a,p)=1$​。 将 $ax\equiv 1\pmod p$ 转化可得 $x...

定义若 $c\mid a$ 且 $c\mid b$，那么称 $c$ 为 $a$ 和 $b$ 的公约数。 在 $a$ 与 $b$ 的所有公约数中，最大的那一个称为最大公约数，记为 $\gcd(a,b)$，在不混淆的情况下亦可记为 $(a,b)$。 性质...

费马小定理定理如果$$ p\in \mathbb{P}\,\, \operatorname{and}\,\, p\not\mid a $$那么有$$ a^{p-1}\equiv 1\pmod p $$ 证明 引理 1若 $a\cdot c\equiv...