::::info[完全剩余系]
通俗来讲，模 m 的完全剩余系就是一个有 m 个元素的集合，其中任意两个数模 m 的余数都不相等。
::::
如果 \{a_0,a_1,\cdots,a_{m-1}\} 是模 m 的完全剩余系，那么对于满足 (b,m)=1 的 b，\{b\times a_0,b\times a_1,\cdots,b\times a_{m-1}\} 也是模 m 的完全剩余系。
证明：
运用反证法。
假设新的集合不是模 m 的完全剩余系，那么存在 b\times a_i 与 b\times a_j 使得：
b\times a_i\equiv b\times a_j\pmod m
那么由于引理一，有：
a_i\equiv a_j\pmod m
那么一开始的集合就也不是模 m 的完全剩余系，与已知条件矛盾。
所以新集合是模 m 的完全剩余系。
费马小定理的证明
易得 \{0,1,2,\cdots,p-1\} 是一个模 p 的完全剩余系。
由于 (a,p)=1，根据引理二，\{0,a,2a,\cdots,(p-1)a\} 也是模 p 的完全剩余系。
我们把两个集合的所有元素（除了 0）全部乘起来再取余，容易得到：
1\times2\times\cdots\times(p-1)\equiv a\times2a\times\cdots\times(p-1)a\pmod p
即
(p-1)!\equiv(p-1)!\times a^{p-1}\pmod p
由于 p 是质数，明显 (p-1)! 与 p 互质。
所以根据引理一，得到
a^{p-1}\equiv1\pmod p
得证。
费马小定理的应用
求乘法逆元是数论中一个很重要的板块。具体来讲，就是要求满足 a\times b\equiv1\pmod m 的 b，此时一般把 b 写作 a^{-1}。
那么对于一个质数 p，对于与它互质的 a，有：
a^{p-1}\equiv1\pmod p\\
a\times a^{p-2}\equiv1\pmod p
所以：
a^{p-2}\equiv a^{-1}\pmod p
这样再加上一个快速幂模板，我们就可以 O(\log p) 求逆元了。
代码如下。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, p;
inline ll quick_power(ll a, ll b, ll mod) { // a 的 b 次方对 mod 取模
ll res = 1;
while (b) {
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int main() {
scanf("%lld%lld", &a, &p);
ll ins = quick_power(a, p - 2, p); // 求逆元
printf("%lld\n", ins);
}
欧拉定理
对于两个数 a,m，如果 (a,m)=1，那么：
a^{\varphi(m)}\equiv1\pmod m
注意：这里的 m 不需要是质数。
::::info[什么是 \varphi(m)]
欧拉函数 \varphi(m) 就是 1 到 m 中与 m 互质的个数，特别的，\varphi(1)=1。
例如：\varphi(6)=2，因为 (1,6)=1，(5,6)=1。
::::
::::info[闲话]
容易发现，如果 m 是质数，那么 \varphi(m)=m-1，所以我们说费马小定理是欧拉定理的特殊版本。
::::
证明
不会证 qwq。
此处给一个感性的理解。
在费马小定理中，我们可以想象成有 p-1 个点，我们在 1 和 a（以下默认要取模）之间连一条有向边，在 a 和 a^2 之间连一条有向边，以此类推，那么乘以 a 的操作就是通过有向边走到下一个顶点，那么从 1 开始走，经过所有边（p-1 条边）后回到原点，说明定理成立。
在欧拉定理中，由于 (a,m)=1，不断乘以 a 后得到的数肯定也与 m 互质，因此我们可以想象成有 \varphi(m) 个点，按照同样的方法连边，从 1 开始走，经过所有边（\varphi(m) 条边）后回到原点，说明定理成立。
我们可以从 2 开始枚举，每次枚举到一个就把 m 里面的这个因子除干净，保证接下来不会找到非质数因子。
由于大于 \sqrt{m} 的质因子只有一个，我们最后只要再判定一下 m 是不是大于 1，是的话就说明还有一个（就是现在的 m）。
代码如下。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m;
int main() {
scanf("%lld", &m);
ll phi = m; // 欧拉函数
for (ll i = 2; i <= sqrt(m); i++) {
if (m % i == 0) {
phi = phi - phi / i; // 避免浮点数精度误差
while (m % i == 0) m /= i;
}
}
if (m > 1) phi = phi - phi / m;
printf("%lld\n", phi);
}