《P4549 【模板】裴蜀定理》

题目描述

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

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

输入格式

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

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

输出格式

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

输入输出样例

输入 #1复制

2 4059 -1782

输出 #1复制

99

说明/提示

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

代码实现：

#include<bits/stdc++.h> using namespace std; int g(int x, int y) { return y ? g(y, x%y) : x; } long long n; int main() { cin >> n; long long res = 0, num; for (int i = 1; i <= n; ++i) { cin >> num; if (num < 0) num = -num; res = g(res, num); } cout << res; return 0; }