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

· · 题解

此题是裴蜀定理的模板题，那么——先上定理内容：

对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且\gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。 ——百度百科

emm,说白了，其实就是两个东西：

\begin{cases}\text{任意}x,y→\gcd(a,b)|ax+by\\ax+by=\gcd(a,b)\text{有整数解}\end{cases}

其中a,b,x,y均为整数

证明

引理①:我已经化成那个样子了，原因显然。
引理②证明：

\text{设}t=\gcd(a,b),\text则 t|a,t|b,t|ax+by \text设 s\text{为}ax+by\text{的最小正整数值, 那么$s$为$a,b$的线性组合} \text{设}r=a\%s,p=\left\lfloor\dfrac{a}{s}\right\rfloor \therefore r=a-ps=a-p(ax+by)=a(1-px)-pby \text{显然$r$也是$a,b$的线性组合} \text{又 $\because s$ 最小，则$r$=0} \text{$\therefore s|a,s|b,$那么$s$为$a,b$的公因数 $\rightarrow t \ge s$} \text{$\because t|ax+by$} \text{$\therefore t|s$} \therefore t \le s \text{$\because t \ge s,t \le s$} \therefore t=s

略去过程QED，由上可知证毕。

回到题目

显然，s即为所求。那么n个数的裴蜀定理怎么弄？每个数的绝对值\gcd一次即可。

代码：

#include<bits/stdc++.h>
using namespace std;

inline int read()//快读
{
    int s=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+ch-48;
        ch=getchar();
    }
    return s*f;
}

inline void write(int x)//快写
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10^48);
}

int n,ans;

int main()//美丽的主程序
{
    n=read(),ans=read();//ans默认为第一个数
    while(--n)ans=__gcd(ans,abs(read()));//懒得手写gcd，虽然NOIP不能用
    write(ans);//输出
    return 0;
}