信奥赛C++提高组csp-s之数论基础专题课：从同余到分数模运算3(案例实践：裴蜀定理)
信奥赛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_{i=1}^nA_i\times X_iS=i=1∑nAi×Xi，使得S > 0 S>0S>0且S SS尽可能的小。
输入格式
第一行一个整数n nn，表示序列元素个数。
第二行n nn个整数，表示序列A AA。
输出格式
一行一个整数，表示S > 0 S>0S>0的前提下S SS的最小值。
输入输出样例 1
输入 1
2 4059 -1782输出 1
99说明/提示
对于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)a1x1+a2x2+⋯+anxn=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，但本题不会出现此情况。
代码实现
#include<bits/stdc++.h>usingnamespacestd;// gcd 函数intgcd(inta,intb){returnb?gcd(b,a%b):a;}intmain(){intn;// 元素个数cin>>n;intans=0;// 初始答案为 0（gcd(0,x)=x）for(inti=0;i<n;++i){inta;// 当前读入的 A_icin>>a;if(a<0)a=-a;// 取绝对值ans=gcd(ans,a);// 与当前答案求 gcd}cout<<ans<<endl;// 输出最小正整数 Sreturn0;}功能分析
- 输入处理：使用
cin读取整数个数和序列，由于n ≤ 20 n \le 20n≤20，输入量很小。 - 求绝对值：对每个数取
abs（此处直接用条件判断if(a<0) a=-a），确保 gcd 处理正数。 - 逐步 gcd：初始化
ans = 0，利用性质gcd ( 0 , x ) = x \gcd(0, x) = xgcd(0,x)=x，依次与每个数求 gcd，最终得到所有数的最大公约数。 - 输出结果：输出该 gcd，即为满足 (S>0) 的最小值。
正确性：根据裴蜀定理，任意整数线性组合能取到的最小正数就是这些数的最大公约数，故答案正确。
复杂度：求 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
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html
3、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.html
4、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}