题解 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$一次即可。 ### 代码： ```cpp #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; } ```