UVA10407题解
12345678hzx
·
·
题解
前置知识
$2.$ **[排序](https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F/1066239?fr=aladdin)**
## 思路
对于每一个数 $x$，我们都可以将其拆分成 $x=y \times d+r$ 的形式。设 $x_1\le x_2$，那么 $x_1-x_2$ 就等于 $(y_2 \times d+r)-(y_1 \times d+r)=(y_2-y_1) \times d$。那么显然，题目就是要我们找出这一列数的差分数组的最大公因数。
至于具体的实现，笔者觉得比较难的点在于读入和求最大公因数的过程中，接下来我们就把这些难点逐个击破。
## 难点击破
$1.$ **读入**
这里的难点在于判断有没有读完，我们直接用 ```while``` 读入，当遇到 $0$ 时就退出。
$2.$ **最大公因数**
求两个数的最大公因数，可以用辗转相除法，$\gcd(a,b)=\gcd(a,b \bmod a)$，以下是辗转相除法的代码。
```cpp
int gcd(int a,int b) {
if(a%b==0) return b;
return gcd(a,a%b);
}
```
当然，你也可以使用 ```__gcd```，这是 C++ 自带的函数，它的作用是返回两个数的最大公因数。
## 代码
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#include<queue>
#include<stack>
#include<vector>
#include<ctime>
#include<map>
#include<set>
#include<bitset>
#include<list>
using namespace std;
int n,a[1005];
int main() {
while(1) {
n=0;
while(1) {
cin>>a[++n];
if(a[n]==0) break;
}
if(a[1]==0) break;
sort(a+1,a+n);
int ans=a[2]-a[1];
for(int i=3;i<n;i++) ans=__gcd(ans,a[i]-a[i-1]);
cout<<ans<<"\n";
}
return 0;
}
```