2022 ICPC 杭州(待补)

A.Modulo Ruins the Legend

题解中说明：其实d只用取0或者1 因为相当于对每个位置加上一个平均数 也就只加了ns 但是可能这个平均数可能为分数 所以d取1和0即可代表所有情况

#include <bits/stdc++.h>
#define endl "\n"
#define INF 0x3f3f3f3f
#define LLINF 0x3f3f3f3f3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

ll exgcd(ll a, ll b, ll& x, ll& y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, x, y);
    ll tx = x;
    x = y, y = tx - y * (a / b);
    return d;
}

signed main() {
    IOS;
    ll n, mod; cin >> n >> mod;
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
        ll t; cin >> t;
        sum += t;
    }

    ll a = n, b = n * (n + 1) / 2;
    ll s, dt;
    ll d = exgcd(a, b, s, dt);
    sum %= mod;

    ll k, t;
    ll g = exgcd(d, mod, k, t);

    ll z = (mod - sum + g - 1) / g;
    (k *= z) %= mod;
    
    s = ((s % mod * k) % mod + mod) % mod, dt = ((dt % mod * k) % mod + mod) % mod;

    cout << (z * g + sum - mod) << endl;
    cout << s << " " << dt << endl;
}