【exgcd】“范式杯”2023牛客暑期多校训练营1 M

秒速五厘米 2024-03-17 21:32 67阅读 0赞

[M-Water\_“范式杯”2023牛客暑期多校训练营1 (nowcoder.com)][M-Water_2023_1 _nowcoder.com]

题意：

![ff87e06944b54d399060a97db18955f8.png][]

思路：

设两个杯子的容量分别为A,B

那么就有：

![A\*k1+B\*k2=X][A_k1_B_k2_X]

手模几次样例可以发现，最少操作次数是![2\*(k1+k2)][2_k1_k2]或![2\*abs(k1-k2)-1][2_abs_k1-k2_-1]

exgcd把一组最小整数解![(k1,k2)][k1_k2]求出来之后，在该特解附近统计答案的最小值

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    const int mod=998244353;
    
    int A,B,X,k1,k2;
    
    int exgcd(int a,int b,int &k1,int &k2){
        if(!b){
            k1=1;
            k2=0;
            return a;
        }
        int d=exgcd(b,a%b,k2,k1);
        k2-=(a/b)*k1;
        return d;
    }
    void solve(){
        cin>>A>>B>>X;
        int D=exgcd(A,B,k1,k2);
        if(X%D){
            cout<<-1<<'\n';
            return;
        }
        k1=k1*X/D;
        int r=B/D;
        k1=(k1%r+r)%r;
        k2=(X-A*k1)/B;
        int ans=1e9;
        for(int t=-10;t<=10;t++){
            int k3=k1+(B/D)*t;
            int k4=k2-(A/D)*t;
            if(k3>=0&&k4>=0){
                ans=min(ans,2*(k3+k4));
            }else{
                ans=min(ans,2*abs(k3-k4)-1);
            }
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[M-Water_2023_1 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/57355/M
[ff87e06944b54d399060a97db18955f8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/7c8151eb8f344ea0a047b21cfd4559d1.png
[A_k1_B_k2_X]: https://latex.csdn.net/eq?A*k1&plus;B*k2%3DX
[2_k1_k2]: https://latex.csdn.net/eq?2*%28k1&plus;k2%29
[2_abs_k1-k2_-1]: https://latex.csdn.net/eq?2*abs%28k1-k2%29-1
[k1_k2]: https://latex.csdn.net/eq?%28k1%2Ck2%29