题目地址:http://codeforces.com/contest/1244/problem/C

题目:


求满足等式的x,y,z值:

wx+dy=p

x+y+z=n

且w>d,

 

解题思路:


网上的题解都说是使x+y的值最小,好像并不是吧,我在题目中并没有找到原话,题目好像只是要求wx>dy(应该是这样吧)。

为了保证wx>dy和z>0,由于w>d,所以应该尽量使x的值大一些,y的值小一些。

  • 方法1:枚举法

对于满足等式的一组解(x0,y0),那么必有(x0+d,y0-w), (x0+2d,y0-2w),(x0+3d,y0-3w)。。。满足上述两个等式,但是又因为y要>=0,所以当y0-kw<w时,无法再更新答案了,若此时的z>=0,那么就找到了解,否则无解。

[0,w)内枚举y的值即可,1e5的时间复杂度,可行。

  • 方法2:扩展欧几里得

如果直接用扩展欧几里德求解方程wx+dy=p的话,x *= p/gcd(w,d); y *= p/gcd(w,d);很可能会超时,且无法保证满足题目wx>dy的要求。

先使wx+dy=p中x的值最大,赢的场数win=p/w,剩下的分数leftp=p%w,剩下的分数全部用于平局,能够完成平局draw=leftp/d,最终还会剩下leftp=leftp%d分数没有得到分配(如果leftp不能完全分完)。

现在考虑改变win和draw的值,使得leftp被分配完,所以问题转化为wx'+dy'=leftp的求解。对于此线性方程,根据扩展欧几里得原理知,如果gcd(w,d) | leftp,那么此线性方程有解,否则无解。

如果有解,更新win和draw值(原始的值分别加上wx'+dy'=leftp对应的解),但是可能值更新完后win<0 || draw<0 || n-win-draw<0的情况,所以需要对win值和draw值做调整。

现在相当于求出了wx+dy=p通解中的定值部分,如下图:

若对win和draw做调整,只需+/-后面的部分,在更新过程中如果更新的值不满足win>=0 && draw>=0 && n-win-draw>=0,说明无解。

 

ac代码:


枚举:

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
    ll n, p, w, d;
    cin >> n >> p >> w >> d;
    bool f = 0;
    for(ll y = 0; y < w; y++)
    {
        if((p-y*d)%w == 0)
        {
            ll x = (p-y*d)/w;
            if(x >= 0 && x+y <= n)
            {
                printf("%lld %lld %lld", x, y, n-x-y);
                f = 1;
                break;
            }
        }
    }
    if(!f) printf("-1");
    return 0;
}

扩展欧几里得:

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n, p, w, d, x, y, win, draw;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll r = exgcd(b, a%b, x, y);
    ll t = x;
    x = y;
    y = t - a/b*y;
    return r;
}
bool solve()
{
    ll leftp = p%w;
    win = p/w, draw = leftp/d, leftp = leftp%d;//平局分完还剩下的分数
    ll gcd = exgcd(w, d, x, y);//wx+dy = gcd(w,d)
    if(leftp%gcd == 0)//可再分配,相当于wx+dy=leftp有解
    {
        ll t = leftp/gcd;
        win += t*x;//最终结果先加上已经确定的值, x,y可能是负数
        draw += t*y;
        ll k1 = d/gcd, k2 = w/gcd;//通解的变化部分,且k2>k1
        while(win < 0)
        {
            win += k1;
            draw -= k2;
            if(draw < 0) return false;
        }
        while(draw < 0)
        {
            win -= k1;
            draw += k2;
            if(win < 0) return false;
        }
        while(n-win-draw < 0)//让win+draw减小,z>=0
        {
            win += k1;
            draw -= k2;
            if(win < 0 || draw < 0) return false;
        }
        if(win >= 0 && draw >= 0 && win+draw <= n)
            return true;
    }
    return false;
}
int main()
{
    cin >> n >> p >> w >> d;
    if(solve()) printf("%lld %lld %lld\n", win, draw, n-win-draw);
    else printf("-1");
    return 0;
}