Link

ICPC2022Hangzhou A Modulo Ruins the Legend

Question

求 $$\sum\limits_{i=1}^n a_i+n\times s+\frac{n(n+1)}{2}\times d \mod m$$ 的最小值

Solution

我们把这个式子看成一一个二元不定方程

$ax+by+sum \mod m$ 的最小值，其中 $a=n,b=\frac{n(n+1)}{2},sum=\sum\limits_{i=1}^n a_i$

先来看 $ax+by (ax+by>0) \mod m$ 下的最小值

根据裴蜀定理可得

\[ax+by=k_1 \times \gcd(a,b) \]

设 $g_1=\gcd(a,b),g2=\gcd(a,b,m)$

式子就转化为求 $k_1g_1 (k_1g_1>0)\mod m$ 的最小值

由于 $k_1g_1 \mod m \Leftrightarrow k_1g_1+tm$

根据裴蜀定理可得

\[k_1g_1+tm=k_2\times g_2 \]

这个值一定大于零，所以 $k_2>0$ 由于需要 $k_1g_1 \mod m$ 最小，则 $k_2$ 取 $1$，则最小值就是 $g_2$

加入 $sum$ 之后，也就是改一下最终的式子

\[sum+k_2g_2=ans \]

这里的 $k_2$ 没有 $k_2>0$ 的限制，只需要 $sum +k_2g_2>0$ 就好了，即

\[ans=sum \mod g_2 \]

如何求 $x,y$ ？

用拓展欧几里得求出 $k_1,t$ 然后再用一次拓展欧几里得求出 $x,y$

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL  exgcd(LL a,LL b,LL &x,LL &y){
    if(!b){x=1,y=0;return a;}
    LL d=exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return d;
}
int main(){
    freopen("A.in","r",stdin);
    LL N,M,sum=0;
    cin>>N>>M;
    for(int i=0;i<N;i++){
        LL x;cin>>x;sum+=x;
    }
    LL a,b,x,y,k1,t;
    a=N,b=N*(N+1)/2;
    LL g1=__gcd(a,b),g2=__gcd(g1,M);
    LL ans=sum%g2;

    exgcd(g1,M,k1,t);
    k1*=((ans-sum)/g2)%M;
    k1%=M;

    exgcd(a,b,x,y);
    x*=k1,y*=k1;

    cout<<ans<<endl;
    cout<<(x%M+M)%M<<" "<<(y%M+M)%M<<endl;
    return 0;
}