牛客练习赛60——斩杀线计算大师

题目传送

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K Special Judge,
64bit IO Format: %lld

题目描述

算术能力是每个炉石玩家必不可少的，假设现在有三种伤害卡，伤害值分别是a,b,c。并且每种伤害卡的数量你可以认为是无限的。现在牛牛想知道是否存在一种方式可以刚好造成k点伤害，输出x,y,z分别表示三种伤害卡的使用个数。
数据保证一定存在解。如果存在多组解，输出任意一组。

输入描述:

一行四个整数分别表示a,b,c,k

输出描述:

一行输出三个整数分别表示x,y,z

示例1
输入

3 4 5 20

输出

4 2 0

备注:
1 ≤ a , b , c ≤ 1e5
0 ≤ k ≤ 1e12

• 题意：

就是多少个a+多少个b+多少个c=k
问你这个“多少个”分别是什么

题解

1. 方法一

把题目改成公式形式就是
ax+by+cz=k
没错，其实就是exgcd，只不过exgcd是ax+by=k
你把咱们这个式子再变变形
就能得到：
a x + b y = k - c * z
而这个z我们可以枚举
那就是a x + b y = k - c * i
题目说了肯定有解，那放心枚举i就完事了
把后面这部分-ci当做整体M
ax+by=M
然后就是exgcd的步骤
用exgcd求出x0,y0
ax0+by0=GCD(a,b)
两边同时除以gcd（a，b）
(gcd(a,b)我们用w代替)
两边除以w，再乘c
ax0+by0-gcd(a,b)+by*c/gcd(a,b)=c

如果w=1
x = x0 + b * t
y = y0 - a * t
且对任一正数t，皆成立
根据这个我们就可以求出方程所有解
t = b / w
x= ( x % t + t ) % t
有空专门整理一下exgcd原理和博客

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod =1e9+3;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    ll d;
    d=exgcd(b,a%b,y,x);
    y=y-a/b*x;
    return d;
}//exgcd模板 
int main()
{
    ll a,b,c,k,x,y;
    scanf("%lld%lld%lld%lld",&a,&b,&c,&k);
    for(ll i=0;i<k/c;i++)
    {
        ll ans=(k-i*c);//去掉c*i的剩余部分
        ll w = exgcd(a,b,x,y);
        if(ans%w)continue;

        x= x * ans / w;
        y= y * ans / w;

        x=( x % ( b / w ) + ( b / w ) ) % ( b / w );
        y= ( ans - x * a ) / b;

        if(x>=0&&y>=0)
        {
            cout<<x<<" "<<y<<" "<<i;
            return 0;
        }



    }
}

2. 方法二

公式还有个变形方式：
k-ax-by=cz
(k-ax-by)/c=z
也就是( k - a x - b y ) % c = = 0
( k - a i - b j ) % c = = 0
枚举i和j就ok了

 for(i)
 {
     for(j)
     {
         if( k - a i - b j ) % c = = 0
         {
         cout<<;
         }
     }
 }

曾经noip好像考过ecgcd裸题感兴趣可以做做