时间限制：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裸题感兴趣可以做做
京公网安备 11010502036488号