题目链接:https://codeforces.com/gym/104090/problem/A
题解:
转化一下发现只需要求满足下式的解:
\[ns+\dfrac{n\times (n+1)}{2}d \equiv C(\bmod m)
\]
设 \(a=n,b=\dfrac{n(n+1)}{2},p=gcd(a,b)\)
即找到一组 \((s',d',t')\) 使得 \(as'+bd'+mt'=C\)
考虑 \(as+bd=p\) 的解 \((s,d)\)
记 \(g=gcd(p,m)\)
\[pk+mt=g
\]
左右同时乘以 \(c=\dfrac{C}{g}\) (由 C 的性质可知 \(g|C\))
得到 \(pkc+mtc=C\)
因此我们就得到了原式的一组解:\(s'=s\times k\times c, d' = d\times k\times c\)
代码:
// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back
using namespace std;
typedef long long ll;
typedef long long LL;
const int inf = 1e9, INF = 0x3f3f3f3f;
int n,m;
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=1,y=0;
return a;
}
ll gd = exgcd(b,a%b,x,y);
ll t = x;x = y;y = t-a/b*y;
return gd;
}
signed main(){
ll sum=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);
sum += x;
}
ll a = n, b = 1ll*n*(n+1)/2,x,y,k,t;
ll p = exgcd(a,b,x,y);
ll g = exgcd(p,m,k,t);
ll C = ((m-sum%m-1) / g+1) * g;
ll c = C / g;
printf("%lld\n%lld %lld\n",(C+sum)%m,(x*k%m*c%m+m)%m,(y*k%m*c%m+m)%m);
return 0;
}