A. Modulo Ruins the Legend
\(题目即求（sum+n*s+(n+1)*n/2*d）\equiv \mod m的最小值\)
\(由裴蜀定理可得n*s+(n+1)*n/2*d=gcd(n,(n+1)*n/2)\)
\(令p=gcd(n,n*(n+1)/2)\)
\(可以表示为(sum+k*p+t*m)\equiv \mod m\)
\(令g=gcd(p,m)\)
\((sum+g*z)%m\)
\(sum+g*z>=m时存在最小值\)
\(因为g*z相当于可以表示出所有可以被%m表示出的值\)
\(所以只需要计算第一个刚好越过的值即可\)
点击查看代码
int exgcd(int a,int b,int &x,int &y){
if(!b){
x=1,y=0;return a;
}
int ans= exgcd(b,a%b,y,x);
y=y-(a/b)*x;
return ans;
}
int inv(int x) { return qpw(x, mod - 2); }
void solve(){
int n,m,x,y;cin>>n>>m;
int sum=0;
for(int i=1;i<=n;i++)cin>>x,sum+=x;
sum%=m;
int s,d;int p=exgcd(n,n*(n+1)/2,s,d);
int t,k;
int g=exgcd(p,m,k,t);
int z=(m-sum+g-1)/g;
cout<<z*g+sum-m<<'\n';
k=k*z%m;
s=(s*k%m+m)%m,d=(d*k%m+m)%m;
cout<<s<<" "<<d<<'\n';
}