bzoj 1441: Min （gcd+裴蜀定理）

Description

Input

Output

Sample Input

Sample Output

HINT

Source

题解：gcd+裴蜀定理

gcd(a,b)就是最小的可以表示成ax+b*y的正整数。

所以我们直接对于所有读入的a求gcd即可

因为x,y的正负是不确定的，所有完全可以用x,y来实现a,b的正负，所以直接忽略a的符号即可。

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>using namespace std;int n;int gcd(int x,int y){	int r;	while (y) {		r=x%y;		x=y; y=r;	}	return x;}int main(){	freopen("a.in","r",stdin);	scanf("%d",&n);	int a1,a2; 	scanf("%d",&a1); 	if (a1<0) a1=-a1;	for (int i=2;i<=n;i++){		scanf("%d",&a2); 		if (a2<0) a2=-a2;		a1=gcd(a1,a2);	}	PRintf("%d/n",a1);}