沭阳奥体小区做网站保定seo外包公司

张

张建站

2026/4/11 4:50:13

10分钟阅读

沭阳奥体小区做网站,保定seo外包公司,中国国际技术智力合作公司官网,个人网站开发项目报告信奥赛C提高组csp-s之数论基础专题课#xff1a;从同余到分数模运算2(知识详解#xff1a;同余、裴蜀定理、扩展欧几里得、乘法逆元、分数模运算) 课程目标理清脉络#xff1a;理解同余、裴蜀定理、扩展欧几里得、乘法逆元、分数模运算之间的逻辑关系。掌握核心#xff1…信奥赛C提高组csp-s之数论基础专题课从同余到分数模运算2(知识详解同余、裴蜀定理、扩展欧几里得、乘法逆元、分数模运算)课程目标理清脉络理解同余、裴蜀定理、扩展欧几里得、乘法逆元、分数模运算之间的逻辑关系。掌握核心熟练运用扩展欧几里得算法求解不定方程及逆元。实战应用能够解决相关的数论模板题和简单变式题。第二部分知识点详解与数学实例1. 同余定义如果两个整数 a 和 b 除以正整数 m 所得的余数相等则称 a 和 b 关于模 m 同余记作a ≡ b ( m o d m ) a \equiv b \pmod{m}a≡b(modm)。数学例子23 ≡ 2 ( m o d 7 ) 23 \equiv 2 \pmod{7}23≡2(mod7)因为23 ÷ 7 3 23 \div 7 323÷73余 2 2 ÷ 7 2 \div 72÷7 0 余 2。100 ≡ 1 ( m o d 99 ) 100 \equiv 1 \pmod{99}100≡1(mod99)。同余的两种等价理解方式整除角度m ∣ ( a − b ) m \mid (a-b)m∣(a−b)即a − b a-ba−b能被m mm整除方程角度存在整数k kk使得a b k ⋅ m a b k \cdot mabk⋅m同余的核心性质性质说明公式自反性自己和自己同余a ≡ a ( m o d m ) a \equiv a \pmod{m}a≡a(modm)对称性左右可互换若a ≡ b ( m o d m ) a \equiv b \pmod{m}a≡b(modm)则b ≡ a ( m o d m ) b \equiv a \pmod{m}b≡a(modm)传递性可传递相等关系若a ≡ b ( m o d m ) a \equiv b \pmod{m}a≡b(modm)b ≡ c ( m o d m ) b \equiv c \pmod{m}b≡c(modm)则a ≡ c ( m o d m ) a \equiv c \pmod{m}a≡c(modm)可加减性同余式可加减若a ≡ b ( m o d m ) a \equiv b \pmod{m}a≡b(modm)c ≡ d ( m o d m ) c \equiv d \pmod{m}c≡d(modm)则a ± c ≡ b ± d ( m o d m ) a \pm c \equiv b \pm d \pmod{m}a±c≡b±d(modm)可乘性同余式可相乘若a ≡ b ( m o d m ) a \equiv b \pmod{m}a≡b(modm)c ≡ d ( m o d m ) c \equiv d \pmod{m}c≡d(modm)则a c ≡ b d ( m o d m ) ac \equiv bd \pmod{m}ac≡bd(modm)幂运算同余式可乘方若a ≡ b ( m o d m ) a \equiv b \pmod{m}a≡b(modm)则a n ≡ b n ( m o d m ) a^n \equiv b^n \pmod{m}an≡bn(modm)2. 裴蜀定理贝祖定理定义标准形式对于任意整数 ( a, b )存在整数 ( x, y )使得 ax by gcd ⁡ ( a , b ) \gcd(a, b)gcd(a,b)。特别地如果gcd ⁡ ( a , b ) 1 \gcd(a, b) 1gcd(a,b)1则存在 ( x, y ) 使得 ax by 1 。更一般地对于任意整数a 1 , a 2 , … , a n a_1,a_2,…,a_na1,a2,…,an不全为零存在整数 x 1 , x 2 , … , x n x_1,x_2,…,x_nx1,x2,…,xn使得a 1 x 1 a 2 x 2 ⋯ a n x n g c d ⁡ ( a 1 , a 2 , … , a n ) a_1x_1a_2x_2⋯a_nx_ngcd⁡(a_1,a_2,…,a_n)a1x1a2x2⋯anxngcd⁡(a1,a2,…,an).等价表述整数 d 是 a,b的线性组合即 daxby有整数解的充要条件是 d是 gcd⁡(a,b)的倍数。gcd⁡(a,b) 是 a和 b的线性组合中绝对值最小的正整数。数学例子取 a 6, b 9 gcd ⁡ ( 6 , 9 ) 3 \gcd(6, 9) 3gcd(6,9)3。存在 ( x -1, y 1 )使得6 × ( − 1 ) 9 × 1 3 6\times(-1) 9\times 1 36×(−1)9×13。取 a 5, b 7 gcd ⁡ ( 5 , 7 ) 1 \gcd(5, 7) 1gcd(5,7)1。存在 ( x 3, y -2 )使得5 × 3 7 × ( − 2 ) 1 5\times 3 7\times (-2) 15×37×(−2)1。3. 扩展欧几里得算法作用给定 ( a, b )递归地计算gcd ⁡ ( a , b ) \gcd(a, b)gcd(a,b)以及一组特解 ( x, y ) 满足 ax by gcd ⁡ ( a , b ) \gcd(a, b)gcd(a,b)。数学推导实例求 47x 30y 1的解。执行欧几里得算法47 30 × 1 17 47 30\times 1 174730×11730 17 × 1 13 30 17\times 1 133017×11317 13 × 1 4 17 13\times 1 41713×1413 4 × 3 1 13 4\times 3 1134×314 1 × 4 0 4 1\times 4 041×40(GCD为1)回代 (扩展欧几里得核心)由13 − 4 × 3 1 13 - 4\times 3 113−4×31代入4 17 − 13 4 17 - 13417−13:13 − ( 17 − 13 ) × 3 1 13 - (17 - 13)\times 3 113−(17−13)×3113 × 4 − 17 × 3 1 13\times 4 - 17\times 3 113×4−17×31代入13 30 − 17 13 30 - 171330−17:( 30 − 17 ) × 4 − 17 × 3 (30 - 17)\times 4 - 17\times 3 (30−17)×4−17×330 × 4 − 17 × 7 1 30\times 4 - 17\times 7 130×4−17×71代入17 47 − 30 17 47 - 301747−30:30 × 4 − ( 47 − 30 ) × 7 1 30\times 4 - (47 - 30)\times 7 130×4−(47−30)×7130 × 11 − 47 × 7 1 30\times 11 - 47\times 7 130×11−47×71所以( x -7, y 11 ) 是方程 47x 30y 1 的一组解。4. 乘法逆元定义若a × x ≡ 1 ( m o d m ) a \times x \equiv 1 \pmod{m}a×x≡1(modm)则称x 是 a 模m的逆元记作a − 1 ( m o d m ) a^{-1} \pmod{m}a−1(modm)。存在逆元的充要条件是gcd ⁡ ( a , m ) 1 \gcd(a, m) 1gcd(a,m)1。数学例子求 5 模 7 的逆元。即找x使5 x ≡ 1 ( m o d 7 ) 5x \equiv 1 \pmod{7}5x≡1(mod7)。由刚才的裴蜀定理例子5 × 3 7 × ( − 2 ) 1 5\times 3 7\times (-2) 15×37×(−2)1。两边同时对 7 取模( 5 × 3 ) m o d 7 0 ≡ 1 ( m o d 7 ) (5\times 3) \ mod \ 7 0 \equiv 1 \ (mod \ 7)(5×3)mod70≡1(mod7)。所以$ 5\times 3 \equiv 1 \pmod{7}$。因此5 模 7 的逆元是 3。5. 分数模运算 (Modular Fraction)定义计算b a ( m o d m ) \frac{b}{a} \pmod{m}ab(modm)的值前提是gcd ⁡ ( a , m ) 1 \gcd(a, m) 1gcd(a,m)1。方法转化为b × a − 1 ( m o d m ) b \times a^{-1} \pmod{m}b×a−1(modm)。数学例子计算8 5 ( m o d 7 ) \frac{8}{5} \pmod{7}58(mod7)。首先5 模 7 的逆元是 3 (如上例)。那么8 5 ( m o d 7 ) ≡ 8 × 3 ( m o d 7 ) 24 ( m o d 7 ) 3 \frac{8}{5} \pmod{7} \equiv 8 \times 3 \pmod{7} 24 \pmod{7} 358(mod7)≡8×3(mod7)24(mod7)3。验证5 × 3 15 ≡ 1 ( m o d 7 ) 5 \times 3 15 \equiv 1 \pmod{7}5×315≡1(mod7)而8 ≡ 1 ( m o d 7 ) 8 \equiv 1 \pmod{7}8≡1(mod7)所以1/5 相当于 31 × 3 3 1 \times 3 31×33结果正确。更多系列知识请查看专栏《信奥赛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;}