给定一个长度为 n 的整数序列 a_1、a_2、……、a_n ，可以选择俩个整数个s , d 将 a_i 均加上 s + id 并需要对操作后的新序列和对 m 取模后最小。
考察知识点 ：
扩展欧几里得算法(exgcd)
解题过程 :
ans \mod m = ans - k_1\ast m= \sum_{i = 0}^{n} a_i + ns + \frac{n\ast (n+1)}{2}sum = \sum_{i=0}^na_i\therefore ns + \frac{n\ast (n+1)}{2} = ans - k_1\ast m - sum = \gcd(n , \frac{n\ast (n + 1)}{2})\ast k_2 g_1 = gcd(n , \frac{n\ast (n + 1)}{2}) k_1m + k_2g_1 = ans - sum = \gcd(m ,g_1)\ast zg_2 = \gcd(m , g_1)\because 0 <= ans < m \therefore -sum <= g2\ast z < m - sum \therefore z_{min} = \frac{-sum}{g2}
### 代码实现：
```c++
#include <bits/stdc++.h>
using namespace std ;
typedef __int128 i128 ;
typedef long long i64 ;
const int inf = 0x3f3f3f3f ;
i64 gcd(i64 a,i64 b) {
return b ? gcd(b , a % b) : a ;
}
i64 exgcd(i64 a,i64 b,i128 &x,i128 &y) {
if ( !b ) {
x = 1 , y = 0 ;
return a ;
}
i64 d = exgcd(b , a % b , y , x) ;
y -= a / b * x ;
return d ;
}
void solve() {
i64 n , m , sum = 0 ;
cin >> n >> m ;
for(int i = 1 ; i <= n ; i++) {
int x ; cin >> x ;
sum += x ;
}
i64 g1 = gcd(n , n * (n + 1) / 2 ) ;
i64 g2 = gcd(m , g1) ;
i64 kmin = -sum / g2 ;
i128 k1 , k2 , s , d ;
i64 d1 = exgcd(m , g1 , k1 , k2) ;
k1 *= kmin ;
k2 *= kmin ;
i64 ans = (d1 * kmin + sum) % m ;
i64 d2 = exgcd(n , n * (n + 1) / 2 , s , d) ;
s *= k2 ;
d *= k2 ;
s = (s % m + m) % m , d = (d % m + m) % m ; // 0 <= s , d < m
cout << ans << '\n' << (i64) s << ' ' << (i64) d ;
}
int main()
{
ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt", "w",stdout);
#endif
int t = 1 ;
// cin >> t ;
while ( t-- ) {
solve() ;
}
return 0 ;
}
```