题解 P4549【【模板】裴蜀定理】

· · 个人记录

这题是 裴蜀定理 的模板题，这里给出证明、拓展

裴蜀定理

存在整数 x,y 使 ax+by=(a,b)，其中可用 辗转相除法 证明，辗转相除法如下：

设求 (u_0,u_1)，则：

u_0=q_0u_1+u_2,0<u_2<|u_1| u_1=q_1u_2+u_3,0<u_3<u_2 u_2=q_2u_3+u_4,0<u_4<u_3 \cdots\cdots,\cdots\cdots u_{k-2}=q_{k-2}u_{k-1}+u_k,0<u_k<u_{k-1} u_{k-1}=q_{k-1}u_k+u_{k+1},0<u_{k+1}<u_k u_k=q_k+u_{k+1}

停止

u_{k+1}=(u_0,u_1) \to u_{k+1}$ 可以用 $u_0,u_1$ 表示 $\to u_0x+u_1y=u_{k+1}=(u_0,u_1)

现证明裴蜀定理：不定方程 ax+by=c 有整数解的充分必要条件是 (a,b)|c

必要性

若 ax+by=c 有整数解

(a,b) | a,(a,b)|b \to (a,b) | ax+by=c

充分性

若 (a,b)|c，则 ax+by=c （有整数解）\Leftrightarrow \dfrac{a}{(a,b)}x+\dfrac{b}{(a,b)}y=\dfrac{c}{(a,b)} 有整数解。

接下来只需证 (a,b)=1 有整数解即可。

ax+by=c \Leftrightarrow x=\dfrac{c-by}{a}

只需找 y 使 a|c-by，即 by \equiv c \pmod{a}

考虑 y=1,2,\cdots,a

当 (a,b)=1 时：

对于不同的 y_1,y_2(1 \le y_1,y_2 \le a), by_1\not\equiv by_2 \pmod{a} \Leftrightarrow b(y_1-y_2) \not\equiv 0 \pmod{a}

|y_1-y_2|\le a-1

故存在 y 使得 by \equiv c \pmod{a}

故存在整数解。

充分性另证

由裴蜀定理知存在整数 x,y 使 ax+by=(a,b) \to a\times x \times \dfrac{c}{(a,b)} + b \times y \times \dfrac{c}{(a,b)}=c

综上所述，得出结论：不定方程 ax+by=c 有整数解的充分必要条件是 (a,b)|c。

因此得出代码：

#include<bits/stdc++.h>
using namespace std;
int gcd(int x, int y) {
    return y?gcd(y,x%y):x;
}
int main(){
    int n;
    cin>>n;
    int ans=0,tmp;
    for(int i=1;i<=n;i++){
        cin>>tmp;
        if(tmp<0) tmp=-tmp;
        ans=gcd(ans,tmp);
    }
    cout<<ans;
    return 0;
}