信奥赛C提高组csp-s之数论基础专题课从同余到分数模运算3(案例实践裴蜀定理)课程目标理清脉络理解同余、裴蜀定理、扩展欧几里得、乘法逆元、分数模运算之间的逻辑关系。掌握核心熟练运用扩展欧几里得算法求解不定方程及逆元。实战应用能够解决相关的数论模板题和简单变式题。第三部分案例实战裴蜀定理研究案例P4549 裴蜀定理题目描述给定一个包含n nn个元素的整数序列A AA记作A 1 , A 2 , A 3 , . . . , A n A_1,A_2,A_3,...,A_nA1​,A2​,A3​,...,An​。求另一个包含n nn个元素的待定整数序列X XX记S ∑ i 1 n A i × X i S\sum\limits_{i1}^nA_i\times X_iSi1∑n​Ai​×Xi​使得S 0 S0S0且S SS尽可能的小。输入格式第一行一个整数n nn表示序列元素个数。第二行n nn个整数表示序列A AA。输出格式一行一个整数表示S 0 S0S0的前提下S SS的最小值。输入输出样例 1输入 12 4059 -1782输出 199说明/提示对于100 % 100\%100%的数据1 ≤ n ≤ 20 1 \le n \le 201≤n≤20∣ A i ∣ ≤ 10 5 |A_i| \le 10^5∣Ai​∣≤105且A AA序列不全为0 00。思路分析裴蜀定理对于任意整数a 1 , a 2 , … , a n a_1, a_2, \dots, a_na1​,a2​,…,an​存在整数x 1 , x 2 , … , x n x_1, x_2, \dots, x_nx1​,x2​,…,xn​使得a 1 x 1 a 2 x 2 ⋯ a n x n gcd ⁡ ( a 1 , a 2 , … , a n ) a_1 x_1 a_2 x_2 \cdots a_n x_n \gcd(a_1, a_2, \dots, a_n)a1​x1​a2​x2​⋯an​xn​gcd(a1​,a2​,…,an​)并且该gcd ⁡ \gcdgcd是能表示的最小正整数。因此本题要求S ∑ A i × X i 0 S \sum A_i \times X_i 0S∑Ai​×Xi​0的最小值答案就是所有A i A_iAi​的最大公约数考虑绝对值因为符号不影响公约数。步骤读入 n 和序列 A。初始化答案变量为 0。对每个A i A_iAi​取绝对值后与当前答案求最大公约数更新答案。输出最终答案。注意由于输入中可能有负数取绝对值再求 gcd。若所有数均为 0题目保证不全为 0则答案应为 0但本题不会出现此情况。代码实现#includebits/stdc.husingnamespacestd;// gcd 函数intgcd(inta,intb){returnb?gcd(b,a%b):a;}intmain(){intn;// 元素个数cinn;intans0;// 初始答案为 0gcd(0,x)xfor(inti0;in;i){inta;// 当前读入的 A_icina;if(a0)a-a;// 取绝对值ansgcd(ans,a);// 与当前答案求 gcd}coutansendl;// 输出最小正整数 Sreturn0;}功能分析输入处理使用cin读取整数个数和序列由于n ≤ 20 n \le 20n≤20输入量很小。求绝对值对每个数取abs此处直接用条件判断if(a0) a-a确保 gcd 处理正数。逐步 gcd初始化ans 0利用性质gcd ⁡ ( 0 , x ) x \gcd(0, x) xgcd(0,x)x依次与每个数求 gcd最终得到所有数的最大公约数。输出结果输出该 gcd即为满足 (S0) 的最小值。正确性根据裴蜀定理任意整数线性组合能取到的最小正数就是这些数的最大公约数故答案正确。复杂度求 gcd 的时间复杂度为O ( log ⁡ max ⁡ ∣ A i ∣ ) O(\log \max|A_i|)O(logmax∣Ai​∣)总复杂度O ( n log ⁡ M ) O(n \log M)O(nlogM)。更多系列知识请查看专栏《信奥赛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;}