codeforces 1244C (思维 or 扩展欧几里得）

题意分析

已知 n , p , w, d ，求x , y, z的值，他们的关系为：

x + y + z = n

x * w + y * d = p

思维法

当 y < w 的时候，我们最多通过1e5次枚举确定答案

而当 y >= w 的时候，平局所得分为：y * d = (y-w)*d + w*d ，可以看作平局的局数为 y - w ，多出的w*d贡献给 (w*d)/w = d 局胜局，所以胜局为 x + d ，说明此时用x+y局胜局和平局得到的分数可以由 x + d + y - w 局胜局和平局得到，同时此时的胜局+平局次数更少，所以枚举 y > w 的情况是没有意义的，完全可以通过枚举 y = {0 ~ w - 1} 得到答案

综上所述，我们只需要在 [0,w) 范围内枚举y即可得到答案

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<queue>

#include<string>

#include<fstream>

#include<vector>

#include<stack>

#include <map>

#include <iomanip>

#define bug cout << "**********" << endl

#define show(x, y) cout<<"["<<x<<","<<y<<"] "

#define LOCAL = 1;

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;

const int mod = 1e9 + ;

const int Max = 5e3 + ;

ll n, sum;

ll win, draw;

int main()

{

#ifdef LOCAL

    //    freopen("input.txt", "r", stdin);

    //    freopen("output.txt", "w", stdout);

#endif

    scanf("%lld%lld%lld%lld", &n, &sum, &win, &draw);

    for(ll y =  ; y < win ; y ++)

    {

        if ((sum - y * draw) % win)

            continue;

        ll x = (sum - y * draw) / win;

        if(x +  y <= n && x >= )

        {

            printf("%lld %lld %lld\n",x,y,n-x-y);

            return ;

        }

    }

    printf("-1\n");

    return ;

}

扩展欧几里得法

扩展欧几里得算法才是这个题目的正解，从式子：x * w + y * d = p 中，可以看出其正好对应扩展欧几里得公式：x * a + y * b = gcd(a,b) ，借助扩展欧几里得公式，我们可以得到x * w + y * d = p的一组解，具体步骤如下：

1）用扩展欧几里得公式求：

x0 * w + y0 * d = gcd(w,d)

得到了x0,y0

2）将上述式子两边同乘 k = p / gcd(w,d) ，【必须保证 (p % gcd(w,d)) == 0 ，否则无解】，得到：

x0 * k * w + y0 * k * d = gcd(w,d) * k

即

x0 * k * w + y0 * k * d = p

这样, x = x0*k , y = y0*k 就是式子 x * w + y * d = p 的一组解，

3）由于x,y,z需要满足

　　x + y + z = n

因此，我们通过调整x,y，使得上式得以满足，为此，我们需要让x + y 的值尽量小；注意到 w > d ，说明当 y 取最小值的时候，x + y 取最小值，如果此时 x + y <= n ，说明有解，否则无解

又根据 x * w + y * d = p ，我们得知 y 每次变化：+- w/gcd(w,d) ，所以y 的最小值即为

y = ( y0 * k ) % (w/gcd(w,d))

4）最后，根据得到的y，求出x 和 z 的值，随后，判断 x + y 是否小于 n ，满足即输出 x , y , z，否则说明无解

（注意求 y 的时候进行取模操作，不然会爆 long long ）

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<queue>

#include<string>

#include<fstream>

#include<vector>

#include<stack>

#include <map>

#include <iomanip>

#define bug cout << "**********" << endl

#define show(x, y) cout<<"["<<x<<","<<y<<"] "

#define LOCAL = 1;

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;

const int Max = 5e3 + ;

ll n, sum;

ll win, draw;

ll exgcd(ll a, ll b, ll &x, ll &y)

{

    if (b == )

    {

        x = ;

        y = ;

        return a;

    }

    ll r = exgcd(b, a % b, x, y);

    ll t = x;

    x = y;

    y = t - (a / b) * y;

    return r;

}

int main()

{

#ifdef LOCAL

    //    freopen("input.txt", "r", stdin);

    //    freopen("output.txt", "w", stdout);

#endif

    scanf("%lld%lld%lld%lld", &n, &sum, &win, &draw);

    ll x, y;

    ll gcd = exgcd(win, draw, x, y);

    if ((sum % gcd) == )

    {

        ll mod = win / gcd;

        y = ((y%mod)*(sum/gcd%mod)%mod + mod)%mod;

        x = (sum - y * draw) / win;

        if(x >=  && y >=  && x + y <= n)

        {

            printf("%lld %lld %lld\n",x,y,n-x-y);

            return ;

        }

    }

    printf("-1\n");

    return ;

}

巴特西

codeforces 1244C (思维 or 扩展欧几里得）

题意分析

思维法

扩展欧几里得法

最新文章

热门文章