牛客练习赛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
问你这个“多少个”分别是什么

题解

方法一

把题目改成公式形式就是
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;}} }

方法二

公式还有个变形方式：
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裸题感兴趣可以做做

总结

以上是生活随笔为你收集整理的牛客练习赛60 ~ 斩杀线计算大师的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。