P4549 【模板】裴蜀定理

题目描述

给定一个包含 n 个元素的整数序列 A，记作 A1​,A2​,A3​,...,An​。

求另一个包含 n 个元素的待定整数序列 X，记 S=i=1∑n​Ai​×Xi​，使得 S>0 且 S 尽可能的小。

输入格式

第一行一个整数 n，表示序列元素个数。

第二行 n 个整数，表示序列 A。

输出格式

一行一个整数，表示 S>0 的前提下 S 的最小值。

输入输出样例

输入 

2
4059 -1782

输出 

99

说明/提示

对于 100% 的数据，1≤n≤20，∣Ai​∣≤105，且 A 序列不全为 0。

代码

无注释版

#include<bits/stdc++.h>
#define int long long
using namespace std;
int ans;
signed main(){int n;cin>>n;for(int i=1;i<=n;i++){int x;cin>>x;if(x<0) x=-x;ans=__gcd(ans,x); }cout<<ans<<"\n";
} 

有注释版

#include<bits/stdc++.h>  // 引入标准库，包含常用的C++库
#define int long long  // 定义 long long 为 int 类型，保证处理较大的数值时不会溢出
using namespace std;  // 使用标准命名空间int ans;  // 用来存储最终的结果，即最小的 Ssigned main(){int n;cin >> n;  // 输入整数 n，表示序列的元素个数// 循环遍历序列 A 中的每个元素for(int i = 1; i <= n; i++){int x;cin >> x;  // 输入第 i 个元素 x// 如果 x 是负数，则取其绝对值if(x < 0) x = -x;// 使用最大公约数（GCD）更新 ans，最小化 S 需要找到序列元素的公约数// `__gcd` 是 C++ 标准库提供的计算两个数最大公约数的函数ans = __gcd(ans, x); }cout << ans << "\n";  // 输出最终结果 ans，即 S 的最小值
}