卡掉自己的但是不会调
查看原帖
卡掉自己的但是不会调
818475
ChpyX2楼主2024/3/31 11:09
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200005;
ll n,p,w,d,x,y,z;
ll exgcd(ll a, ll b, ll &x, ll &y) { 
    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    } else {
        ll d = exgcd(b, a % b, y, x);
        y -= (a / b) * x;
        return d;
    }
}
bool func(ll a, ll b, ll c, ll &x, ll &y) {
    ll d = exgcd(a, b, x, y);
    cout<<x<<' '<<y;
    if(c % d != 0) return false;
    x *= c / d;
    y *= c / d;cout<<x<<' '<<y;
    if(x+y>n){
      ll q=(x+y-n)/(a-b);
      x+=(b/d)*q;
      y-=(a/d)*q;
    }
    if(y<0)return false;
    cout<<x<<' '<<y<<' '<<n-x-y<<'\n';
    return true;
}
int main(){
  cin>>n>>p>>w>>d;
  if(!func(w,d,p,x,y))cout<<-1<<'\n';
  return 0;
}//xw*yd=p x+y+z=n

88 88 88 87 可以卡掉(其实好像n,n,n,n−1n,n,n,n-1都行

思路是先求通解再找到合法的x和y,z直接做减法

2024/3/31 11:09
加载中...