标签：gcd 题解 sum ICPC2022Hangzhou k1 1g Ruins LL mod

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;
}

标签：gcd,题解,sum,ICPC2022Hangzhou,k1,1g,Ruins,LL,mod
From： https://www.cnblogs.com/martian148/p/17872833.html