CF1593D1题解
naroto2022
·
·
题解
CF1593D1题解
题意
把题意转换一下就可以得到：给定一个数列 a_1,a_2,a_3,\cdots,a_n，要求一个数列 b（b 中的数为非负整数）和一个正整数 k，使得 a[1]-b[1]\times k=a[2]-b[2]\times k=\cdots=a[n]-b[n]\times k。若有无数多个 k，请输出 -1。（有多组数据）
思路
首先直接讲解法：将数组去重并判断是否有无数多个 k 之后再两两作差求最大公因数即可。那么就有以下解释：
- 咋去重？答：建立一个 vis 数组和 a 数组，vis 数组为判断一个数是否已经出现过，a 数组为去重之后的数组，如果一个数没有出现过，就录入到数组 a 中。
- 咋判断有无数多个 k？答：在去重的时候，用一个 len 记录去重之后的数组长度，如果为 1，也就是去重以前所有数都相同，所以 k 为任意数，输出 -1。
- 为啥用两两相减求最大公因数？接下来我就来证明。
证明：
\because a_i-b_i\times k=a_j-b_j\times k
\therefore a_i-a_j=k\times(b_i-b_j)
\therefore a_i\equiv a_j\pmod k
\therefore a_1\equiv a_2\equiv a_3\equiv\cdots\equiv a_n\pmod k
### 总结
1. 多组数据。
2. 换行。
3. 两两作差求最大公因数。
4. 去重。
5. 特判。
### 代码
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int T;
int n,a[45],ans,cnt,len;
bool vis[2000005];
//a数组为去重之后的数组
//cnt为临时变量。
//len为去重之后的数组长度。
//vis数组是一个数字是否出现过的统计数组，去重要用。
int gcd(int a, int b){//求最大公因数
if(b==0) return a;
return gcd(b,a%b);
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
memset(vis,0,sizeof(vis));//一定要重置。
len=0;
for(int i=1; i<=n; i++){
scanf("%d",&cnt);
if(vis[cnt+1000001]==0){//以前这个数没出现过（这个数是新的）。
vis[cnt+1000001]=1;//标记为出现过（旧的）。
a[++len]=cnt;//录入a数组
}
}
if(len==1){//去重之后只有1个数，也就是去重以前所有数都相同，所以k为任意数，输出-1。
printf("-1\n");//别忘了换行
continue;
}
ans=abs(a[2]-a[1]);//取绝对值
for(int i=2; i<len; i++)
for(int j=i+1; j<=len; j++)
ans=gcd(ans,abs(a[j]-a[i]));
printf("%d\n",ans);
}
return 0;
}
```
### 附（选看）
#### 怎么求最大公因数
方法 $1$：用唯一分解定理，先分解质因数，然后求最大公因数。
令 $a=p_1^{a_1}\times p_2^{a_2}\times p_3^{a_3}\times \cdots p_m^{a_m}$，$b=p_1^{b_1}\times p_2^{b_2}\times p_3^{b_3}\times \cdots p_m^{b_m}$。
则 $\gcd(a,b)=p_1^{\min(a_1,b_1)}\times p_2^{\min(a_2,b_2)}\times p_2^{\min(a_2,b_2)}\times\cdots p_m^{\min(a_m,b_m)}$。
方法 $2$：九章算术 $\bullet$ 更相减损术。
$\forall a,b\in \mathbb{N}$，$b\le a$，有 $\gcd(a,b)=\gcd(b,a-b)=\gcd(a,a-b)$。
$\forall a,b\in \mathbb{N}$，有 $\gcd(2a,2b)=2\gcd(a,b)$。
证明：
对于 $a$，$b$ 的任意公约数 $d$，因为 $d\vert a$，$d\vert b$，所以 $d\vert (a-b)$。因此，$d$ 为 $b$，$(a-b)$ 的公约数。反之亦成立。
方法 $3$：欧几里得算法。
$\forall a,b\in \mathbb{N}$，$b\neq0$，$\gcd(a,b)=\gcd(b,a\bmod b)$。
证明：
若 $a<b$，则 $\gcd(b,a\bmod b)=\gcd(a,b)$，命题成立。
若 $a\geq b$，设 $a=q\times b+r$，其中 $0\le r<b$。显然 $r=a\bmod b$。对于 $a$，$b$ 的任意公约数 $d$，因为 $d\vert a$，$d\vert q\times b$，所以 $d\vert (a-qb)$。即 $d\vert r$，因此，$d$ 为 $b$，$r$ 的公约数。反之亦成立。所以他们的最大公因数相等。
代码实现：
```cpp
int gcd(int a, int b){
if(b==0) return a;
return gcd(b,a%b);
}
```