CSAcademy Round #63 (Div. 2 only) Find Remainder

题目链接https://csacademy.com/contest/round-63/task/find-remainder/
题意:给你nab,要求找满足条件的最小正整数k,使每组均满足a\%k=b,若没有输出-1
思路:如果每组a都等于b,则输出a中最大的数加一,如果出现a小于b,则易知不存在解。然后我们把等式转换一下,得到(a-b)\%k=0,所以对于所有组,这个k都是他们差值的约数,所以我们可以先对所有a-b求最大公约数,然后去找这个最大公约数的一个最小约数满足大于最大的b即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI=acos(-1.0);
const int P=1000000007;
const int N=1e5;
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while (ch<'0' || ch>'9') _f|=(ch=='-'),ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
ll a[N+5],b[N+5];
int main(){
    int n;
    ll ans=0,mx=0,mxa=0;
    read(n);
    bool flag=true,flag2=true;
    for (int i=1;i<=n;i++) read(a[i]),mxa=max(mxa,a[i]);
    for (int i=1;i<=n;i++) read(b[i]),mx=max(mx,b[i]),flag2&=a[i]==b[i];
    if (flag2) return printf("%lld\n",mxa+1),0;
    for (int i=1;i<=n;i++){
        if (!flag) break;
        if (b[i]>a[i]) flag=false;
        ans=__gcd(ans,a[i]-b[i]);
    }
    if (mx>=ans) flag=false;
    if (!flag) puts("-1");
    else{
        ll m=sqrt(ans+0.5);
        ll tmp=ans;
        for (int i=1;i<=m;i++){
            if (ans%i==0){
                if (i>mx) tmp=min(tmp,i*1LL);
                if (ans/i>mx) tmp=min(tmp,ans/i);
            }
        }
        printf("%lld\n",tmp);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注