题解 P4549 【【模板】裴蜀定理】
JustinRochester
2019-02-14 13:40:33
这里给出非递归的 gcd 做法
---
**【分析】**
--
要看证明内容的就麻烦翻一下别人的题解了，这里本蒟蒻就不班门弄斧了，直接讲一下解题思路：
显然，就是对于读入的 $n$ 个数，输出他们的最大公因数
假设 $gcd(a,b)=g,gcd(a,b,c)=d$
由 $d|a$ 且 $d|b$ 得 $d|gcd(a,b)$ 即 $d|g$
又 $\because d|c$
$\therefore d|gcd[\quad gcd(a,b),c\quad]$
因此，我们只要对每次读入的一个数，和上几次得出的最大公因数用一次 gcd 即可
当然，因为答案要求正数，所以读入的负数直接转化为正数即可
----
接下来开始讲非递归 gcd 的原理，不求甚解的同学或者一看就懂的 dalao 麻烦往下跳
常规的 gcd ，是用递归实现的：
```cpp
int gcd(int a,int b){
if(b==0) return a;
else return gcd(b,a%b);
}
```
当然，在压行选手眼中，它是这样的：
```cpp
int gcd(int a,int b) { return (!b)?a:gcd(b,a%b); }
```
今天呢，我这边给出非递归打发。这是我在一篇文章中看到的黑科技：
我们想，$gcd(a,b)=gcd(b,a\%b)=...=gcd(r,0)$ 所以 $r$ 为最大公因数。
那么，实际上就是说，递归边界是 $b==0$ 这个应该很显然吧
而当 C++ 中的 while() 循环，内部是一个赋值表达式的时候
一旦赋值过后的该值为 $0$ ，就会退出循环
这和我们的递归边界是很像的。
而对于 $(a,b)$ 变成 $(b,a\%b)$ ，可以理解为：
1. $(a,b)$ 变为 $(a\%b,b)$
2. $(a\%b,b)$ 交换两个值，变为 $(b,a\%b)$
这两步的合成
而对于交换两个不同的数 $a,b$ ，有一个黑科技打法：
```cpp
a^=b^=a^=b;
```
程序从右往左执行：
1. a^=b,a 变成 a^b
2. b^=a,b 变成 b^(a^b)=b^b^a=a
3. a^=b,a 变成 (a^b)^a=a^a^b=b
至此，足以完成交换操作
---
实际上，我们把上述步骤结合一下，就可以实现非递归了，这边就直接给出代码了，我觉得应该可以理解了：
```cpp
while(b^=a^=b^=a%=b);
```
最后， $a$ 就是最大公约数
当然，还有一个小细节，大家可以想一想，为什么？
```cpp
int &me=LRJ;
me->output("想一想，为什么");
```
刚刚那个代码的前面应该要加上一个判定，变成：
```cpp
if(b) while(b^=a^=b^=a%=b);
```
---
**【代码】**
--
那本蒟蒻就放 ~~我那码风极丑的~~ 代码了
```cpp
#include<cstdio>
using namespace std;
inline int read(){
register int ans=0;register char c=getchar(); while(c<48||c>57) c=getchar();
while(c>=48&&c<=57) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}//读入优化，并且直接不读负号
int main(){
register int n=read()-1,s=read();
while(n--){
if(s==1) break;
register int tmp=read();
if(tmp) while(tmp^=s^=tmp^=s%=tmp);
}
printf("%d",s);
return 0;
}
```