牛客练习赛66 C公因子题解(区间gcd)

题目链接

题目大意

给你一个长为n的数组,给所有数组元素加上一个非负整数x，使得这个数组的所有元素的gcd最大

题目思路

这主要是设计到一个多个数gcd的性质

gcd(a,b,c,d.....)=gcd(a,b-a,c-b,d-c.....)

其实这个式子很容易证明，设gcd(a,b,c,d...)=x

则\(a=k_1*x,b=k_2*x....\)

显然原式成立

那么直接进行差分操作，显然除了第一个元素，其他元素都不会变化，则\(\max gcd=gcd(b-a,c-b,d-c....)\)

add显然也是可以直接求出来的,因为(add+a[1])%maxgcd==0

代码

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<cstdio>

#include<vector>

#include<string>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<unordered_map>

#define fi first

#define se second

#define debug printf(" I am here\n");

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int maxn=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;

const double eps=1e-10;

int n;

ll a[maxn],dif[maxn];

ll gcd(ll a,ll b){

    return b==0?a:gcd(b,a%b);

}

signed main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++){

        scanf("%lld",&a[i]);

        dif[i]=a[i]-a[i-1];

    }

    ll x=a[1],y=0;

    for(int i=2;i<=n;i++){

        y=gcd(y,abs(dif[i]));

    }

    printf("%lld %lld\n",y,((y-x)%y+y)%y);

    return 0;

}

巴特西

牛客练习赛66 C公因子题解(区间gcd)

题目链接

题目大意

题目思路

代码

最新文章

热门文章

巴特西

牛客练习赛66 C公因子 题解(区间gcd)

题目链接

题目大意

题目思路

代码

最新文章

热门文章

牛客练习赛66 C公因子题解(区间gcd)