Codeforces 1244C The Football Season (解方程)

链接：https://codeforces.com/problemset/problem/1244/C

题意：n场比赛，赢一场加w分，平局加d分，输加0分，总分p分，问赢，平，输的局数, 无解-1。

　　　n<1e12, d<w<1e5, p<1e17

题解：x，y，z肯定不为负数，直接套exgcd的板子是不行的，因为d<w,保证x+y尽可能的小，xw+dy=p,直接枚举系数较小的y即可，y的范围：y<w，因为大于w的时候，不如去增加x，这样x+y的和还能保持尽可能小

#include <bits/stdc++.h>
#define IO_read ios::sync_with_stdio(false);cin.tie(0)
#define fre freopen("in.txt", "r", stdin)
#define _for(i,a,b) for(int i=a; i< b; i++)
#define _rep(i,a,b) for(int i=a; i<=b; i++)
#define lowbit(a) ((a)&-(a))
using namespace std;
typedef long long ll;
template <class T>
void read(T &x)
{
    char c; bool op=0;
    while(c=getchar(), c<'0'||c>'9') if(c=='-') op=1;
    x=c-'0';
    while(c=getchar(), c>='0'&&c<='9') x=x*10+c-'0';
    if(op) x=-x;
}
template <class T>
void write(T x)
{
    if(x<0) putchar('-'), x=-x;
    if(x>=10) write(x/10);
    putchar('0'+x%10);
}

ll ex_gcd(ll a, ll b, ll &x, ll &y)
{
    if(a==0&&b==0) return -1;
    if(b==0) {x=1, y=0; return a;}
    ll d=ex_gcd(b, a%b, y, x);
    y-=a/b*x;
    return d;
}

int main()
{
    ll a, b, p, n;
    read(n), read(p), read(a), read(b);
    /*
    ll x, y, z;
    ll gcd=ex_gcd(a, b, x, y);
    ll k=p/gcd;
    x=k*x, y=k*y, z=n-x-y;
    printf("%I64d %I64d %I64d
", x, y, z);
    */
    //if(a>b) swap(a, b); 要保证枚举的是k系数比较小的 
    for(ll y=0; y<=1e5+5; y++)
    {
        ll x=(p-b*y)/a;
        ll z=n-x-y;
        if(a*x+b*y==p&&x>=0&&z>=0){
            printf("%I64d %I64d %I64d
", x, y, z);
            return 0;
        }
    }
    printf("-1
");
    return 0;
}

Codeforces 1244C The Football Season (解方程)

相关推荐