A. Modulo Ruins the Legend

$$
求 \quad (\sum\limits_{i = 1}^{n} a_{i} + ns + \frac{n(n + 1)}{2}d) \quad % \quad m \quad 最小
$$

$$
由裴蜀定理知 \quad ax + by = k \times gcd(a, b)
$$

$$
令 \quad sum = \sum\limits_{i = 1}^{n} a_{i} \quad \Rightarrow \quad 原式 = sum + k \times gcd(a, b)
$$

$$
(sum + k \times gcd(a, b)) \quad % \quad m \quad = \quad (sum + k \times gcd(a, b) + pm) \quad % \quad m
$$

$$
再一次裴蜀定理 \quad k \times gcd(a, b) + pm = t \times gcd(a, b, m)
$$

$$
即 \quad (sum + t \times gcd(a, b, m)) \quad % \quad m \quad 最小
$$

$$
解得 \quad t = \lceil \frac{m - sum}{gcd(a, b, m)} \rceil \quad 其中 \quad a = n, \quad b = \frac{n(n + 1)}{2}
$$

$$
带回使用Exgcd求解 k, s, d
$$

$$
Exgcd 通解
$$

$$
x = x_{0} + k \times \frac{b}{gcd(a, b)}
$$

$$
y = y_{0} - k \times \frac{a}{gcd(a, b)}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;

long long Exgcd(long long a, long long b, long long& x, long long& y) {
	if (!b) {
		x = 1;
		y = 0;
		return a;
	}
	long long c = Exgcd(b, a % b, y, x);
	y -= (a / b) * x;
	return c;
}

void solve() {
    long long n, m;
    cin >> n >> m;
    long long sum = 0;
    vector<long long> v(n);
    for (auto& x : v) {
        cin >> x;
        sum += x;
    }
    sum %= m;

    long long x1, y1;
    long long a = n;
    long long b = n * (n + 1) / 2;
    long long g1 = Exgcd(a, b, x1, y1);
    long long x2, y2;
    long long g2 = Exgcd(g1, m, x2, y2);
    long long t = (m - sum + g2 - 1) / g2;
    cout << (sum + g2 * t) % m << "\n";
    long long k = x2 * t % m;
    long long s = (x1 * k % m + m) % m;
    long long d = (y1 * k % m + m) % m;
    cout << s << " " << d << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }

    return 0; 
}