P7191 [COCI2007-2008#6] GRANICA

翟翟 · 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;
}

P7191 [COCI2007-2008#6] GRANICA

Code

谢谢大家