营销型网站单页,云浮建设网站,企业门户网站开发平台的设计与实现,北京装修公司排名电话题目传送 时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒 空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K Special Judge, 64bit IO Format: %lld 题目描述 算术能力是每个炉石玩家必不可少的#xff0c;假设现在有三种伤害卡#xff0c;伤害值分别是a,b…题目传送 时间限制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多少个ck 问你这个“多少个”分别是什么
题解
方法一
把题目改成公式形式就是 axbyczk 没错其实就是exgcd只不过exgcd是axbyk 你把咱们这个式子再变变形 就能得到 a x b y k - c * z 而这个z我们可以枚举 那就是a x b y k - c * i 题目说了肯定有解那放心枚举i就完事了 把后面这部分-ci当做整体M axbyM 然后就是exgcd的步骤 用exgcd求出x0,y0 ax0by0GCD(a,b) 两边同时除以gcdab (gcd(a,b)我们用w代替) 两边除以w再乘c ax0by0-gcd(a,b)by*c/gcd(a,b)c
如果w1 x x0 b * t y y0 - a * t 且对任一正数t皆成立 根据这个我们就可以求出方程所有解 t b / w x ( x % t t ) % t 有空专门整理一下exgcd原理和博客
#includebits/stdc.h
using namespace std;
typedef long long ll;
const ll mod 1e93;
ll exgcd(ll a,ll b,ll x,ll y)
{if(!b){x1;y0;return a;}ll d;dexgcd(b,a%b,y,x);yy-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 i0;ik/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(x0y0){coutx y i;return 0;}}
}方法二
公式还有个变形方式 k-ax-bycz (k-ax-by)/cz 也就是( 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裸题感兴趣可以做做
