题解：B3830 [NICA #2] 回溯的雨

· · 题解

简要题意

给你一个数 x 和一个数列 c，请你构造一个数列 a 和一个数 y，使得对于所有的 1\le i \le n，满足 a_i x+y=c_i。

思路分析

实际上，如果我们忽略原式中的 y，即将原式的两端都减去 y，那么有 a_i x=c_i-y，所以如果对于所有的 1\le i \le n，满足 c_i-y 能被 x 整除，那么 a 一定有解，反之无解。

换言之，我们可以得到 c_1 \equiv c_2 \equiv c_3 \equiv\dots\equiv c_n \pmod x。

因此，我们可以以此为依据判断是否有解。

接下来的问题是 y 的最大值怎么求？

这个其实非常好办。既然他要求这些数列是正整数序列，那我就让 c 中的最小值变为 x，即使 a_i=1，这样就可以让其对应的 y 值更大。

代码如下：

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define int long long
int n, x, c[100001];
signed main() {
    ios::sync_with_stdio(0);
    cin >> n >> x;
    for (register int i = 1; i <= n; ++i) cin >> c[i];
    sort(c + 1, c + n + 1);
    if (c[1] < x) {
        cout << "-1\n";
        return 0;
    }
    for (register int i = 2; i <= n; ++i) {
        c[i] -= c[1];
        if (c[i] % x != 0) {
            cout << "-1\n";
            return 0;
        }
    }
    cout << c[1] - x << endl;
    return 0;
}