本文主要是介绍2019.8.9 金华正睿集训总结Day13，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
8.9
我睡过头了！！！！
好饿~~~~噫
简单数论（！？!!!∑(ﾟДﾟノ)ノ）
是的，又是它
先讲了一些基本定义啊之类的
然后从欧几里得开始
提了下裴蜀定理， 即若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。
接着是扩展欧几里得
这个时候讲到了小凯的疑惑
小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币？
设两个面额为 a, b，那么有 (a, b) = 1。其实就是找一个最大的 d，使得 ua + vb = d 没有非负整数解。
取 u = (b − 1), v = −1 或 u = −1, v = (a − 1) 即可。
当然这道题用a*b -（a+b）这个式子直接可以得出答案
证明可见这个博客：https://blog.csdn.net/nimabide_01/article/details/78756525
下面又讲了同余，解同余方程，逆元，剩余系
任何 m 个分别属于 m 个剩余类的数组成剩余系。
简化剩余系
所有的 n 满足 0 < n ≤ m, (n, m) = 1 构成了一个模 m 的简化剩余系。
记这样 n 的个数为 φ(m)
如果 (m, m′) = 1,a 取遍模 m 的简化剩余系， a′ 取遍模 m′的简化剩余系，那么 am′ + a′m 取遍模 mm′ 的简化剩余系。
证明略。
如果 (m, m′) = 1，那么 φ(mm′) = φ(m)φ(m′)
φ(pe) = (p − 1) ∗ pe−1
φ(m) = m ∏p|m(1 − 1/p)
接下来是欧拉定理
然后是一些例题
积性函数，Miller-Rabin 算法，Pollard Rho 算法
筛
用来求 1 ∼ n 里面的素数或者积性函数的值。
用埃氏筛法筛素数的时间复杂度是 O(n log log n)。
欧式筛法的时间复杂度是 O(n) 的。
同时可以筛一些 φ 与 μ
一些定理
拉格朗日定理
对于一个度数为 n 的多项式 F(x)，那么 F(x) ≡ 0 (mod p)至多 min(n, p) 个解。
威尔逊定理
(p − 1)! ≡ −1 (mod p)
考虑 2, 3, · · · , p − 2 这些数都存在逆元，可以两两匹配。
拓展拓展欧几里得（？！）
又讲了原根，狄利克雷卷积，莫比乌斯函数，莫比乌斯反演
一些例题
总结：
C班的数论一样懵逼，简单的还好，有些是真崩溃
其中部分内容在另一篇总结中有写，这里不再重复，附上链接：https://mp.csdn.net/mdeditor/98311484#
对于数学不及格的人来说，这是道过不去的坎~~
这篇关于2019.8.9 金华正睿集训总结Day13的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
