洛谷P4549 【模板】裴蜀定理

题目
学习博客

定理内容：

对于任何\(a,b \in Z\)和他们的最大公约数\(d\)，关于未知数\(x\)和\(y\)的线性不定方程\(ax+by=c\)有整数解\((x,y)\)当且仅当\(d|c\)，可知有无穷多组解。特别的，一定存在整数使\(ax+by=d\)成立

推论：

\(a,b\)互质的充要条件是存在整数\(x,y\)使\(ax+by=1\)。

证明:

设\(gcd(a,b)=d\)
易得：\(d|a\)，\(d|b\)
又\(\because\) \(x\in Z,y\in Z\)
继而可得：\(d|ax+by\)
好像证完了

关于本题就是将两个变量推广到了多个变量
求\(n-1\)遍\(gcd\)即可
代码也是简洁到家

#include <cstdio>
#include <iostream>
using namespace std;
int n, ans, x, y;
int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') w = -1; ch = getchar();}
    while(isdigit(ch)) {s = s * 10 + ch - '0'; ch = getchar();}
    return s * w;
}
int gcd(int x, int y) {
//  if(x < 0) x = -x;
//  if(y < 0) y = -y;
    return y == 0 ? x : gcd(y, x % y); 
}
int main() {
    n = read();
    x = read(), y = read();
    if(x < 0) x = -x;
    if(y < 0) y = -y;
    ans = gcd(x, y);
    for(int i = 1; i <= n - 2; i++) {
        y = read();
        if(y < 0) y = -y;
        ans = gcd(ans, y);
//      x = ans;
    }
    cout << ans << endl;
    return 0;
}

谢谢收看，祝身体健康！

洛谷P4549 【模板】裴蜀定理

原文：https://www.cnblogs.com/yanxiujie/p/11706679.html