526互联

数论初步

发布时间 2023-12-19 20:12:11作者: wangxuzhou

裴蜀定理

思路

不定方程 \(ax+by=c\) 成立的充要条件为 \(\gcd(a,b)|c\)。

证明：

有 \(\gcd(a,b)|ax,\gcd(a,b)|by\)
\(∴\gcd(a,b)|ax+by\)
\(∴\gcd(a,b)|c\)

扩展：

不定方程 \(\displaystyle\sum_{i=1}^n (a_i\times b_i)=c\) 成立的充要条件为 \(\gcd(a_1,a_2,a_3,...,a_n)|c\)。

证明同理。

例题

【模板】裴蜀定理

显然，由于 \(\gcd(a_1,a_2,a_3,...,a_n)|s\)，最小的 \(s\) 就是 \(\gcd(a_1,a_2,a_3,...,a_n)|s\)。

#include <bits/stdc++.h>
using namespace std;
int n, x, ans;
int main() {
    cin >> n;

    while (n--) {
        cin >> x;
        x = abs(x);

        if (!ans)
            ans = x;
        else
            ans = __gcd(ans, x);
    }

    cout << ans;
    return 0;
}