URAL 1252 ——Sorting the Tombstones——————【gcd的应用】

#include<stdio.h>
#include<algorithm>
#include<bits/stdc++.h>
#include<string.h>
#include<bitset>
#include<math.h>
#include<iostream>
using namespace std;
const int maxn = 1e6;
struct Stone{
    int wei,idx;
}stones[maxn];
int GCD(int a,int b){
    return b == 0? a : GCD(b,a%b);
}
bool cmp1(Stone a,Stone b){
    return a.wei < b.wei;
}
bool cmp2(Stone a,Stone b){
    return a.wei > b.wei;
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i = 1; i <= n; i++){
            scanf("%d",&stones[i].wei);
            stones[i].idx = i;
        }
        sort(stones+1,stones+1+n,cmp1);
        int nn = 0, ans = 0, gcd = 0;
        for(int i = 1; i <= n; i++){
            int tmp = abs(i - stones[i].idx);
            if(tmp){
                nn++; gcd = GCD(gcd,tmp);
            }
        }
        if(nn == 0){
            ans = n -1;
        }
        ans = max(ans,gcd-1);
        sort(stones+1,stones+1+n,cmp2);
        nn = 0, gcd = 0;
        for(int i = 1; i <= n; i++){
            int tmp = abs(i-stones[i].idx);
            if(tmp){
                nn++;
                gcd = GCD(gcd,tmp);
            }
        }
        if(nn == 0){
            ans = n-1;
        }
        ans = max(ans,gcd-1);
        printf("%d\n",ans);
    }
    return 0;
}

/*
5
30
21
56
40
17
*/