P4549 裴蜀定理

题目描述

给定一个包含 $n$ 个元素的整数序列 $A$，记作 $A_1,A_2,A_3,...,A_n$。

求另一个包含 $n$ 个元素的待定整数序列 $X$，记 $S=\sum _{i=1}^n{A}_i\times X_i$，使得 $S>0$ 且 $S$ 尽可能的小。

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

2
4059 -1782

样例输出 #1

99

提示

对于 $100\%$ 的数据，$1\le n\le 20$，$|A_i|\le 10^5$，且 $A$ 序列不全为 $0$。

solution

题干中的“$A_i\times X_i$，使得 $S>0$ 且 $S$ 尽可能的小”，联想到裴蜀定理中的ax+by = gcd(a, b)，其实问题也就转化为求这n个数的最大公倍数。
注意，a是整数，可能为负，取绝对值后再用gcd()

#include<iostream>
#include<algorithm>
using namespace std;

int gcd(int a, int b){
	return b == 0 ? a : gcd(b, a % b);
}

int main(){
	int n, a, s = -1;
	scanf("%d", &n);
	while(n--){
		scanf("%d", &a);
		if(s < 0) s = abs(a);
		else s = gcd(s, abs(a));//a是整数，可能为负数，负数和正数的gcd一定是负数==>转化为绝对值的gcd，满足s > 0且不影响计算 
	}
	printf("%d", s); 
	return 0;
}