洛谷4549 裴蜀定理

https://www.luogu.org/problemnew/show/P4549

这都是些什么破题啊..

$$\text{设}S=\sum_{1\le i\le n}{A_ix_i}\text{，其中}x_i\in Z\text{，要求最小化}S\text{使得}S>0\\\text{设}d=gcd\left( A_1,A_2…..,A_n \right) \\\text{设}A_i=dk_i\\\text{则}S=d\sum_{1\le i\le n}{k_ix_i}\\\text{显然,当}\sum_{1\le i\le n}{k_ix_i}=\text{1时}S\text{最小}\\\text{假设}n\ge \text{2，那么则令所有}x_i=0\left( i>2 \right) \\\text{设}a=k_1,b=k_2\\\text{则等价于解方程}ax_1+bx_2=1\\\text{因为}a\text{与}b\text{互质，所以方程}ax_1+bx_2=\text{1一定有整数解}\\\text{所以}S\text{最小值为}d$$

// luogu-judger-enable-o2
#include <iostream>

using int_t = long long int;

using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 20;
int_t seq[LARGE + 1];
int_t n;

int_t gcd(int_t a, int_t b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

int main()
{
    cin >> n;
    for (int_t i = 1; i <= n; i++)
    {
        cin >> seq[i];
        if (seq[i] < 0)
            seq[i] *= -1;
    }
    if (n == 1)
        cout << seq[1] << endl;
    else
    {
        int_t gcd = ::gcd(seq[1], seq[2]);
        for (int_t i = 3; i <= n; i++)
        {
            gcd = ::gcd(gcd, seq[i]);
        }
        cout << gcd << endl;
    }
    return 0;
}