数论2：同余，欧拉函数，逆元
同余
\[a\equiv b (\mathrm{mod\,\,} m) \leftrightarrow m|b-a\\ a\equiv b(\mathrm{mod\,\,} m), a\equiv b (\mathrm{mod\,\,}n)\rightarrow a\equiv b(\mathrm{mod\,\,}[m,n])\\ \bbox[yellow]{ (k,m)=d, ka\equiv ka'(\mathrm{mod\,\,} m)\rightarrow a\equiv a'(\mathrm{mod\,\,} \frac md)} \]
公式三证明：
\[\because (k,m)=d,\therefore(\frac kd, \frac md)=1\\ 又\because m | k(a-a’) \therefore \frac md|\frac kd(a-a’)\\ 又\because \frac md与\frac kd互质， \therefore \frac md | a-a’，得证 \]
公式三更一般的结论：
\[ka\equiv ka'(\mathrm{mod\,\,} m)\rightarrow a\equiv a'(\mathrm{mod\,\,} \frac m{(m,k)}) \]
线性同余方程
\[ax\equiv b(\mathrm{mod\,\,} m)\leftrightarrow ax+my=b \]
对 \(mx\equiv 0(\mathrm{mod\,\,}m),ax\equiv b(\mathrm{mod\,\,}m)\) 辗转相除
还有一种计算方法比较好理解（来自dls）
\[\begin{cases} 100x\equiv 0(\mathrm{mod\,\,}100),(1)\\ 87x\equiv3(\mathrm{mod\,\,}100),(2) \end{cases} \]
\[(1)-(2)得,13x\equiv97(\mathrm{mod\,\,}100),(3)\\ (2)-6\times(-3)得,9x\equiv 21(\mathrm{mod\,\,}100),(4)\\ (3)-(4)得,4x\equiv 76(\mathrm{mod\,\,}100)\\ (4)-2\times(5)得，x\equiv69(\mathrm{mod\,\,}100) \]
简化剩余系
所有的 n 满足 \(0<n\leq m,(n, m)=1\) 构成了一个模 m 的简化剩余系。\(\phi(m)\) 表示 n 的个数。
欧拉函数
\[\phi(m)=m\prod_{p|m}(1-\frac1p) \]
欧拉函数证明
\[积性函数性质 \phi(mn)=\phi(m)\phi(n)和唯一分解定理 n=p_1^{a_1}p_2^{a_2}…p_k^{a_k}\\ 因此\phi(n)=\phi(p_1^{a_1})…\phi(p_k^{a_k}),\\对于任意一项都有 \bbox[yellow]{\phi(p_s^{a_s})=p_s^{a_s}-p_s^{(a_s-1)},(1)}\\ 试证(1):从1到p_s^{a_s}共有p_s^{a_s}个数字，不互质的数有\bbox[yellow]{p_s,2p_s,…,p_s^{a_s-1}}共{p_s^{a_s-1}}项\\ 则互质的数有\bbox[yellow]{p_s^{a_s}-p_s^{a_s-1}}个，即\phi(p_s^{a_s})=p_s^{a_s}-p_s^{a_s-1}=p_s^{a_s}(1-\frac1{p_s})\\ 可以把该式子推广到质数分解的每一项因子，则有:\\ \phi(n)=\phi(p_1^{a_1})…\phi(p_k^{a_k}) =p_1^{a_1}…p_k^{a_k}*(1-\frac1{p_1})…(1-\frac1{p_k})=n\prod_{i=1}^{k}(1-\frac1{p_i}) \]
欧拉函数板子
ll phi (ll n) {
ll ans = n;
for (int i = 2; i*i <= n; i++) {
if (n % i == 0) {
ans = ans / i * (i - 1); //*(1-1/i)
while (n % i == 0) n /= i;
}
}
if (n > 1) ans = ans / n * (n - 1); //还剩下就再乘
return ans;
}
欧拉定理
习题
欧拉函数模板 http://oj.daimayuan.top/course/12/problem/489
原文地址：http://www.cnblogs.com/CTing/p/16791955.html
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，请务用于商业用途!
3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！
8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载
声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性
