数学思维——cf1244C

可惜cf不能用int128,不然这个题就是个exgcd的板子题

这是exgcd的解法，但是只用ll的话会溢出

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll x,y,z,a,b,c,d,n;

ll exgcd(ll a,ll b,ll &x,ll &y){//返回（a,b）
    if(b==0){x=1,y=0;return a;}
    ll d=exgcd(b,a%b,x,y);
    ll z=x;x=y,y=z-a/b*y;
    return d;
}

int main(){
    cin>>n>>c>>a>>b;//1e12,c:1e17,a:1e5,b:1e5 
    d=__gcd(a,b);
    if(c%d!=0){
        puts("-1");return 0;
    }

    exgcd(a,b,x,y);
//923399641127 50915825165227299 94713 49302    
    x*=c/d;y*=c/d;
    ll mod1=b/d,mod2=a/d;

    //先让x，y都变成非负整数
    if(x<0){
        ll k;
        if(x%mod1==0)k=abs(x/mod1);
        else k=abs(x/mod1)+1;
        x+=k*mod1;
        y-=k*mod2;
    }
    else if(y<0){
        ll k;
        if(y%mod2==0)k=abs(y/mod2);
        else k=abs(y/mod2)+1;
        x-=k*mod1;
        y+=k*mod2;
    }

    if(x<0 || y<0){
        puts("-1");return 0;
    }
    if(x>n && y>n){
        puts("-1");return 0;
    }
    //让x+y的值取到最小值
    if(mod1>mod2){
        ll k=x/mod1;
        x-=k*mod1;
        y+=k*mod2;
    }
    else {
        ll k=y/mod2;
        x+=k*mod1;
        y-=k*mod2;
    }
    if(x+y>n){puts("-1");return 0;}
    cout<<x<<" "<<y<<" "<<n-x-y<<"\n";
}

View Code

这是直接枚举的办法

/*
ax+by=c;
x+y+z=n;
b<a<=1e5; c<=1e17; n<=1e12
性质：如果有解，那么一定有y<a的一个解
假设有解 (x,y=y'+a)
ax+b(y'+a)=c
ax+by'+ba=c;
a(x+b)+by'=c,即必定有一个解是(x+b,y')
所以枚举y=[0，a-1]即可
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll n,a,b,c;
int main(){
    cin>>n>>c>>a>>b;
    for(ll y=0;y<a;y++){
        ll t=c-b*y;
        if((t>=0) && t%a==0){
            ll x=t/a;
            if(x+y<=n){
                cout<<x<<" "<<y<<" "<<n-x-y;
                return 0;
            }
        }
    }
    puts("-1");
}