B3830 回溯的雨 题解

· · 题解

简要题意

给出公式 a_{i}x+y=c_{i} 这一公式和 x 与正整数序列 c，让我们求出最大的 y 或在无解的情况下输出 -1。

分析

又是一道数学题，学过小学除法的你肯定能快速地将原式化作 (c_{i}-y) \div x=a_{i}。在这个式子中，不难发现 y 很像除法中的余数。不过不同的是在这个式子中 y 不一定要比 x 小。同时为了保证 y 作为定值一直不变，我们可以先判断整个 c 数组取余 x 的余数是否不变，再排序找到 c 数组的最小值减去 x 就是 y 的最大值啦。
一定要记得开 long long！

代码

#include<bits/stdc++.h>
using namespace std;
long long n,x,c[100010];//记得一定要开long long哦 
int main(){
    cin>>n>>x;
    for(int i=1;i<=n;i++){//输入 
        cin>>c[i];
    }
    sort(c+1,c+1+n);
    long long pd=c[1]%x;//判断余数是否相同 
    for(int i=1;i<=n;i++){
        if(c[i]%x!=pd){
            cout<<-1;
            return 0;
        }
    }
    if(c[1]<x)cout<<-1;//特判一种情况 
    else cout<<c[1]-x;
    return 0;
}

感谢阅读！