信奥赛C提高组csp-s之数论基础专题课从同余到分数模运算1(知识地图同余、裴蜀定理、扩展欧几里得、乘法逆元、分数模运算)课程目标理清脉络理解同余、裴蜀定理、扩展欧几里得、乘法逆元、分数模运算之间的逻辑关系。掌握核心熟练运用扩展欧几里得算法求解不定方程及逆元。实战应用能够解决相关的数论模板题和简单变式题。第一部分知识地图与衔接逻辑这五个知识点可以看成是一条“生产流水线”最终目的是为了解决“分数取模”这个看似复杂的问题。起点同余这是所有问题的背景。我们研究的世界不再是整数而是“模 m 的世界”。在这里所有的数都只关心它除以 m 的余数。核心矛盾在这个世界里加法、减法、乘法都很好用唯独除法不成立例如4 / 2 m o d 6 4/2 \ mod \ 64/2mod6不等于( 4 m o d 6 ) / ( 2 m o d 6 ) (4 mod 6)/(2 mod 6)(4mod6)/(2mod6)。我们要解决的问题就是如何在模世界里做除法工具1裴蜀定理为了在模世界里做除法我们遇到了一个方程a x ≡ 1 ( m o d m ) a x \equiv 1 \ (mod \ m)ax≡1(modm)。这相当于在整数中找 a x m y 1。裴蜀定理告诉我们这个方程有解的前提是 gcd(a, m) 1 互质。它给了我们“解存在的条件”。工具2扩展欧几里得算法既然条件满足了那具体怎么解 a x m y gcd(a, m) 这个方程呢扩展欧几里得算法就是我们用来求解这个方程的“计算器”。它不仅能求出最大公约数 d 还能顺便求出一组整数解 (x, y) 。产物1乘法逆元我们利用扩展欧几里得求解 a x m y 1 解出的 x 就是 a 在模 m 意义下的乘法逆元记作a − 1 a^{-1}a−1。它的意义在模世界里a − 1 a^{-1}a−1就是 ( 1/a )。因为a × a − 1 ≡ 1 ( m o d m ) a \times a^{-1} \equiv 1 \ (mod \ m)a×a−1≡1(modm)。产物2分数模运算有了逆元这个工具除法问题就迎刃而解了。计算b a ( m o d m ) \frac{b}{a} \ (mod \ m)ab(modm)就等于计算b × a − 1 ( m o d m ) b \times a^{-1} \ (mod \ m)b×a−1(modm)。至此我们成功地在模世界里实现了除法知识流程图同余背景 (遇到除法难题)⬇引出线性同余方程 ax ≡ 1 (mod m)⬇裴蜀定理 (判断是否有解: gcd(a,m)1)⬇扩展欧几里得算法 (求解方程 ax my 1)⬇得到乘法逆元 x (a⁻¹)⬇解决分数模运算 b/a ≡ b * a⁻¹ (mod m)更多系列知识请查看专栏《信奥赛C提高组csp-s知识详解及案例实践》https://blog.csdn.net/weixin_66461496/category_13113932.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html4、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}