题解 P4549 【裴蜀定理 / Min】

标题海星，直接给出正解（至少我现在看到的标题是“ 裴蜀定理 / Min”）…… 裴蜀（贝祖）定理，就是关于$x, y$的不定方程$ax + by = c$有整数解的充要条件是$\gcd(a, b)\mid c$。 由此我们发现对于式子$ax+by$的值一定被$\gcd(a, b)$整除，于是就变成了$k\times \gcd(a,b)$。由于$\gcd(a, b)$已知，把它看成常数$a$即可。于是就把两项给合并了。 然后最终就变成了$ax+by$的最小非负值——那当然是$\gcd(a, b)$了。 就这样递推下去就行了，注意由于读入可能为负，读进来的时候取个绝对值即可（由于系数反一下是无关的，所以结果是相同的）。 ```cpp for(int i = 1, t; i <= n; ++i) { scanf("%d", &t); if(t < 0) t = -t; ans = gcd(ans, t); } ```