题解 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)了。

就这样递推下去就行了，注意由于读入可能为负，读进来的时候取个绝对值即可（由于系数反一下是无关的，所以结果是相同的）。

for(int i = 1, t; i <= n; ++i)
{
    scanf("%d", &t);
    if(t < 0)
        t = -t;
    ans = gcd(ans, t);
}