信奥赛C++提高组csp-s之数论基础专题课：中国剩余定理1（数学原理）

信奥赛C提高组csp-s之数论基础专题课中国剩余定理1数学原理中国剩余定理CRT是数论中的一个重要定理在信奥赛NOI系列赛事中属于必须掌握的模板级别知识。它主要用于求解一元线性同余方程组。接下来我们先从数学原理、手算例子进行详细讲解后面文章再举编程题目实战。一、数学角度讲解中国剩余定理1. 定理定义中国剩余定理Chinese Remainder Theorem, CRT用于求解如下形式的同余方程组{ x ≡ a 1 ( m o d m 1 ) x ≡ a 2 ( m o d m 2 ) ⋮ x ≡ a n ( m o d m n ) \begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_n \pmod{m_n} \end{cases}⎩⎨⎧​x≡a1​(modm1​)x≡a2​(modm2​)⋮x≡an​(modmn​)​其中模数 (m 1 , m 2 , . . . , m n m_1, m_2, ..., m_nm1​,m2​,...,mn​)两两互质。2. 标准解法令M m 1 × m 2 × . . . × m n M m_1 \times m_2 \times ... \times m_nMm1​×m2​×...×mn​对于每一个 i 令M i M / m i M_i M / m_iMi​M/mi​由于m i m_imi​与M i M_iMi​互质我们可以找到M i M_iMi​在模m i m_imi​意义下的逆元t i t_iti​即满足M i × t i ≡ 1 ( m o d m i ) M_i \times t_i \equiv 1 \pmod{m_i}Mi​×ti​≡1(modmi​)那么方程组的一个特解为x ∑ i 1 n a i × M i × t i x \sum_{i1}^{n} a_i \times M_i \times t_ix∑i1n​ai​×Mi​×ti​方程组的通解为x x 0 k × M ( k ∈ Z ) x x_0 k \times M \quad (k \in \mathbb{Z})xx0​k×M(k∈Z)在编程竞赛中通常要求输出最小的非负整数解即x m o d M x \mod MxmodM。二、数学手算举例我们用《孙子算经》中的经典问题“物不知数” —— 三三数之剩二五五数之剩三七七数之剩二。求最小正整数解。转化为方程组x ≡ 2 ( mod 3 ) x ≡ 3 ( mod 5 ) x ≡ 2 ( mod 7 ) x \equiv 2 \ (\text{mod} \ 3) \\ x \equiv 3 \ (\text{mod} \ 5) \\ x \equiv 2 \ (\text{mod} \ 7)x≡2(mod3)x≡3(mod5)x≡2(mod7)模数 3, 5, 7 两两互质。计算过程M 3 × 5 × 7 105 M 3 \times 5 \times 7 105M3×5×7105针对第一个方程 (m 1 3 , a 1 2 m_13, a_12m1​3,a1​2)M 1 105 / 3 35 M_1 105 / 3 35M1​105/335求 35 在模 3 下的逆元35 ≡ 2 ( m o d 3 ) 35 \equiv 2 \pmod{3}35≡2(mod3)我们需要找到一个t 1 t_1t1​使得2 × t 1 ≡ 1 ( m o d 3 ) 2 \times t_1 \equiv 1 \pmod{3}2×t1​≡1(mod3)。解得t 1 2 t_1 2t1​2。贡献值a 1 × M 1 × t 1 2 × 35 × 2 140 a_1 \times M_1 \times t_1 2 \times 35 \times 2 140a1​×M1​×t1​2×35×2140针对第二个方程 (m 2 5 , a 2 3 m_25, a_23m2​5,a2​3)M 2 105 / 5 21 M_2 105 / 5 21M2​105/521求 21 在模 5 下的逆元21 ≡ 1 ( m o d 5 ) 21 \equiv 1 \pmod{5}21≡1(mod5)所以t 2 1 t_2 1t2​1。贡献值3 × 21 × 1 63 3 \times 21 \times 1 633×21×163针对第三个方程 (m 3 7 , a 3 2 m_37, a_32m3​7,a3​2)M 3 105 / 7 15 M_3 105 / 7 15M3​105/715求 15 在模 7 下的逆元15 ≡ 1 ( m o d 7 ) 15 \equiv 1 \pmod{7}15≡1(mod7)所以t 3 1 t_3 1t3​1。贡献值2 × 15 × 1 30 2 \times 15 \times 1 302×15×130求和取模特解x 0 140 63 30 233 x_0 140 63 30 233x0​1406330233最小正整数解233 m o d 105 23 233 \mod 105 23233mod10523结果23符合题意23除以3余2除以5余3除以7余2。更多系列知识请查看专栏《信奥赛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;}