贰. 与数论函数联系不大的东西
二.定理
费马小定理&欧拉定理
-
若 \(p\) 为质数且 \(a \not \equiv 0\pmod p\)，则 \(a^{p-1}\equiv 1\pmod p\).
-
若 \(\gcd(a,m)=1\)，则 \(a^{\varphi(m)}\equiv 1\pmod m\).
三.算法
1.欧几里得相关
求 \(\gcd\)
\[\gcd(a,b)=\begin{cases}a & b=0 \\ \gcd(b,a\bmod b) & b\not = 0\end{cases} \]利用这个东西递归计算即可。
扩展欧几里得（exgcd）求解同余方程
- 记 \(g=\gcd(a,b)\)，求解下列方程：\(ax+by=g\)
设计函数 exgcd(ll a,ll b,ll &x,ll &y)。
当 \(b=0\) 时，我们解此时的方程 \(a_0x+b_0y=g=a_0\)，只需令 \(x=1,y=0\) 即可。
若已经知道了 \(bx+(a\bmod b)y=g\) 的一组解 \(x_0,y_0\)，如何借出方程 \(ax+by=g\) 的一组解？
\[\begin{aligned}bx_0+(a\bmod b)y_0&=bx_0+(a-\lfloor \frac{a}{b} \rfloor \cdot b)y_0 \\&=bx_0+ay_0- \lfloor \frac{a}{b} \rfloor \cdot by_0 \\&=a(y_0)+b(x_0-\lfloor \frac{a}{b} \rfloor \cdot y_0)\end{aligned}\]于是我们就得到了一组解 \(x=y_0,y=x_0-\lfloor \frac{a}{b} \rfloor \cdot y_0\)，不停地向上回溯即可解出原方程的解。
代码：
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){ x=1,y=0;return a; }
ll d=exgcd(b,a%b,x,y);
ll z=x; x=y; y=z-y*(a/b);//妈妈生的！！a/b要带括号！！！
return d;
}
-
方程 \(ax+by=c\) 当且仅当 \(\gcd(a,b)\,\mid \,c\) 时有解。
-
解同余方程 \(ax\equiv b\pmod m\) 时，只需解出 \(ax-my=b\) 的一组解即可。当且仅当 \(\gcd(a,m)\,\mid \,b\) 时有解。
//解同余方程 ax≡b(mod m)
ll TYFC(ll a,ll b,ll m){
ll x,y,mm;
ll G=exgcd(a,m,x,y);
if(b%G) return -1;
x*=b/G;mm=m/G;
return (x%mm+mm)%mm;
}
类欧几里得算法
单独写一篇博客了，在这里。
2.其他
（一）筛法
①埃氏筛
\(\color{red}\text{咕咕咕咕咕}\)
②线性筛
\(\color{red}\text{咕咕咕咕咕}\)
标签：总结,方程,gcd,数论,ll,exgcd,mm,ax,同余 From： https://www.cnblogs.com/baoyangawa/p/17999856