牛客练习赛 66C公因子 题解

原题

思路

考场想复杂了,搞到自闭……
实际上,因为差值不变,我们可以先差分,求\(\gcd\),便得到答案(考场时想多了,想到了负数、正数各种复杂的处理,但是不需要),最后处理一下即可

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e6+10;
ll n,a[MAXN],ji[MAXN];
ll gcd(ll x,ll y){
    if(x<y)swap(x,y);
    if(y==0) return x;
    return gcd(y,x%y);
}
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        ji[i]=abs(a[i]-a[i-1]);
    }
    ll i,ans;
    for(i=2;i<=n;i++) if(ji[i]>0) break;
    ans=ji[i];
    for(;i<=n;i++){
        ans=gcd(ans,ji[i]);
    }
    ans=abs(ans);
    printf("%lld %lld",ans,(ans-a[1]%ans)%ans);
    return 0;
}
上一篇:计算机网络-错题记录本


下一篇:近期学的一些小知识