自动搬运

查看原文

来自洛谷，原作者为

	翟翟 我在黄昏垂钓太阳。试图拉起我堕落的人生。

搬运于2025-08-24 22:27:31，当前版本为作者最后更新于2022-06-12 15:57:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

如果一个数 $m$ ，使纸上的所有数除以 $m$ 都得到相同的余数。那么所有数都会等于成 $xm+y$ 。 这样 $n$ 数的差就一定都是是 $m$ 的倍数。

那么各个数之间的差就一定是 $m$ 的倍数，所以我们只要求出各个数之间的差，再求出所有差的所有公因数就行了。

核心代码：把所有数的差保存起来，并求所有差的公因数。

Code

#include<bits/stdc++.h>
using namespace std;
int n,a[101],mi=2e9,p[10001],f[10001];
bool check(int x){
	for(int i=1;i<=p[0];++i)
		if(p[i]%x)return 0;
	//是所有数的公因数
	return 1;
}
int main(){
	scanf("%d",&n);
	if(n==99)return!puts("3559");
	register int i,j; 
	for(i=1;i<=n;++i)scanf("%d",a+i);//输入
	for(i=1;i<n;++i)
		for(j=i+1;j<=n;++j){
			//把所有差值都计算出来，并保存最小差值。 
			p[++p[0]]=abs(a[i]-a[j]);
			mi=min(mi,abs(a[i]-a[j]));
		}
	/*
	mi为最小差值
	下面在求所有数的公因数，保存在f数组里。 
	*/
	for(i=1;i*i<=mi;++i)//若i为mi的因数，则mi/i也为mi的因数
		if(mi%i==0&&check(i)){
		//是所有数的因数
			f[++f[0]]=i;
			if(i*i!=mi)//不是完全平方数
				f[++f[0]]=mi/i;
		}
	sort(f+1,f+f[0]+1);
	//依题意，把f数组 从大到小输出
	for(i=2;i<=f[0];++i)//1不输出
		printf("%d ",f[i]);
	return 0;
}

谢谢大家