裴蜀定理

在数论中，裴蜀等式是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a,b和m，关于未知数 x和y的线性丢番图方程（称为裴蜀等式）：ax+by=m

有整数解时当且仅当m是 a及b的最大公约数d的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解 x、y都称为裴蜀数，可用扩展欧几里得算法求得。

就是关于 $y$ 的不定方程 $=c$  有整数解的充要条件是 g$\mathrm{cd}(a,b)\mid c$ 。

题目见洛谷:P4549

模板

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

int gcd(int ,int ); 


int main() {
	int t,ans = 0;
	cin >> t;
	for(int i = 1;i <= t;++i) {
		int tmp;
		scanf("%d",&tmp);
		if(tmp < 0) tmp = -tmp;
		ans = gcd(ans,tmp);
	}
	cout << ans << endl;
	return 0;
}

int gcd(int x,int y) {
	if(y == 0) return x;
	else return gcd(y,x % y);
}