扩展欧几里得算法

求 $ax + by = c$ ，其中 $a,b,c$ 均为已知， $x,y$ 为未知数，该方程有解的条件是 $c \bmod gcd(a,b)=0$ ，只要有解就有无数个解，具体求解方法是找到一组特解 $x_0,y_0$ ，令 $g=gcd(a,b)$ ，那么 $x=x_0+(b/g)k$ , $y=y_0-(a/g)k$ ，其中k为正整数。以下是求 $x_0$ 和 $y_0$ 的算法

//返回d=gcd(a,b)，并返回ax+by=c的特解x,y
ll extend_gcd(ll a,ll b,ll &x,ll &y){
    if(b==0){x=1;y=0;return a;}
    ll d=extend_gcd(b, a%b, y, x);
    y-=a/b*x;
    return d;
}

解释：

ax + by = k \cdot \gcd(a,b) = \gcd(a,b) = \gcd(b, a\%b) = bx' + (a\%b)y'

\begin{aligned} &= bx' + \left(a - \left\lfloor \frac{a}{b} \right\rfloor \cdot b \right) y' \\ &= a y' + b \left( x' - \left\lfloor \frac{a}{b} \right\rfloor \cdot y' \right) \end{aligned}

那么 $\begin{cases} x = y' \\ y = x' - \lfloor a/b \rfloor \cdot y' \end{cases}$ 。这样一直往下递归，直到b为0，就可以往回带，算出一组特解。例题：牛客月赛111F

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using db = double;
ll extend_gcd(ll a,ll b,ll &x,ll &y){
    if(b==0){x=1;y=0;return a;}
    ll d=extend_gcd(b, a%b, y, x);
    y-=a/b*x;
    return d;
}
int main(){
    std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int n,k;
    cin>>n>>k;
    vector<ll> a(n+1);
    ll mx=0,mn=1e9+10;
    ll sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
        mx=max(mx,a[i]),mn=min(mn,a[i]);
    }
    if(n==k){
        if(mx!=mn) cout<<-1<<endl;
        else cout<<0<<endl;
        return 0;
    }
    ll R=min(mn,(sum-k*mx)/(n-k));
    ll x=0,y=0;
    if(sum%gcd(n,k)){
        cout<<-1<<endl;
        return 0;
    }
    ll g=extend_gcd(n, k, x, y);
    // cout<<x<<" "<<y<<endl;
    x*=sum/g;
    ll tmp=(R-x)*g/k;
    // cout<<tmp<<endl;
    ll ansx=x+k*tmp/g;
    while(ansx>R) ansx-=k/g;
    ll ans=(sum-n*ansx)/k;
    cout<<ans<<endl;
    return 0;
}

思路：从题意可以推出三个式子，然后可以推出x（最后所有数的值）的最大范围，之后会发现满足一个式子 $nx+ky=sum$ ，我们想让x尽量大这样所需要的操作就尽可能少。