cfGlobalRound24--BC补题

B-Doremy's Perfect Math Class

思路：假设答案集合，在普遍的答案集合中找到特别之处.

!!假设!!a1,a2,a3,a4就是某个集合S的答案。

a2-a1=a1，即a2=2*a1.

必然的..因为a2-a1<a2,结果又存在于S中,结果只能是a1.

a3-a2=a1 or a2 ?

假如a3-a2=a2,则a3=2*a2=4*a1.那么a3-a1=3*a1..又3*a1>a2, 3*a1<a3..意味着a2,a3之间还有不存在的数。这是和一开始的假设矛盾的

所以a3-a2=a1,才是合法的.

a4-a3=a1 or a2 or a3 ?

if--a4-a3=a3,则a4=2*a3=6*a1.那么a4-a1=5*a1..又5*a1>a3, 5*a1<a4..意味着a3,a4之间还有不存在的数。这是和一开始的假设矛盾的

if--a4-a3=a2,则a4=5*a1.那么a4-a1=4*a1..又4*a1>a3,4*a1<a4..还是意味着a3,a4,之间还有不存在的数字。这是和一开始的假设矛盾的

那么a4-a3=a1.才是合法的。那么可以发现两个相邻的数字的差值是一定的,是最小的数字a1..意味着答案是一个等差数列

因为是一个等差数列，设公差为d,那么d=a1,且更大的数必然都是a1的倍数.所以答案即是maxn/a1; 但是a1不一定是输入的最小值.

如果单纯记录数组之间的最小差值,或集合本身最小值是不行的:{3,5,7,9}-->{1,2,3,4,5,6,7,8,9};  5-3=2，3-2=1辗转相减，出现了1.----在求gcd的时候，5%3=2,3%2=1--->5-3-2=1;

9%5=4,5%4=1--->9-5-4=1;

{5,25}-->{5,10,15,20,25}

int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
void solve(){       //补B--数学思维
    //偏门：观察样例
    //cout<<__gcd(24,12);
    int n,_gcd=0; cin>>n;
    int maxn=INT_MIN;
    for(int i=1;i<=n;i++){
        int x; cin>>x;
        maxn=max(maxn,x);
        _gcd=gcd(_gcd,x);
    }
    cout<<maxn/_gcd<<endl;
}