【题目来源】
洛谷：P4549 【模板】裴蜀定理 - 洛谷 (luogu.com.cn)
【题目描述】
给定一个包含 \(n\) 个元素的整数序列 \(A\)，记作 \(A_1,A_2,A_3,...,A_n\)。
求另一个包含 \(n\) 个元素的待定整数序列 \(X\)，记 \(S=\sum\limits_{i=1}^{n}A_i×X_i\)，使得 \(S>0\) 且 \(S\) 尽可能的小。
【输入】
第一行一个整数 \(n\)，表示序列元素个数。
第二行 \(n\) 个整数，表示序列 \(A\)。
【输出】
一行一个整数，表示 \(S>0\) 的前提下 S 的最小值。
【输入样例】
2
4059 -1782
【输出样例】
99
【算法标签】
《洛谷 P4549 裴蜀定理》 #数学# #最大公约数,gcd# #不定方程# #Bézout定理#
【代码详解】
#include<iostream>
#include<cmath>
using namespace std;int n, a, s; // n: 数字数量，a: 当前输入的数字，s: 当前的最大公约数// 计算最大公约数（辗转相除法）
int gcd(int a, int b)
{return b == 0 ? a : gcd(b, a % b);
}int main()
{cin >> n; // 读入数字数量for (int i = 1; i <= n; i++){cin >> a; // 读入当前数字s = gcd(s, abs(a)); // 计算当前数字绝对值与前一个最大公约数的最大公约数}cout << s; // 输出所有数字绝对值的最大公约数return 0;
}
// 使用acwing模板二刷
#include <bits/stdc++.h>
using namespace std;int n, a; // n: 数字数量，a: 临时变量// 计算最大公约数（辗转相除法）
int gcd(int a, int b)
{return b ? gcd(b, a % b) : a; // 如果b不为0则递归，否则返回a
}int main()
{cin >> n; // 读入数字数量int res = 0; // 初始最大公约数为0for (int i = 1; i <= n; i++){int a;cin >> a; // 读入当前数字res = gcd(res, abs(a)); // 计算当前数字绝对值与之前结果的最大公约数}cout << res << endl; // 输出所有数字绝对值的最大公约数return 0;
}
【运行结果】
2
4059 -1782
99