首页 > 代码库 > uva 10090 - Marbles(欧几里得+通解)
uva 10090 - Marbles(欧几里得+通解)
题目链接:uva 10090 - Marbles
题目大意:给出n,表示有n个珠子,现在要用若干个盒子来装。有两种盒子,一种价钱c1,可以装t1个珠子,另一种价钱c2,可以装t2个珠子。要求所卖的盒子刚好装n个珠子,并且价钱最小的方案。
解题思路:用拓展欧几里得算法求出xt1+yt2=n的一对解x′和y′,这样就有通解:
x=x′ngcd(t1,t2)+t2gcd(t1,t2)k
y=y′ngcd(t1,t2)?t1gcd(t1,t2)k
然后根据性价比选择一种盒子的个数尽量多。
#include <cstdio>
#include <cstring>
#include <cmath>
typedef long long ll;
ll n, c1, t1, c2, t2;
void gcd (ll a, ll b, ll& d, ll& x, ll& y) {
if (!b) {
d = a;
x = 1;
y = 0;
} else {
gcd(b, a%b, d, y, x);
y -= (a/b)*x;
}
}
int main () {
while (scanf("%lld", &n) == 1 && n) {
scanf("%lld%lld%lld%lld", &c1, &t1, &c2, &t2);
ll d, xi, yi, x, y;
gcd(t1, t2, d, xi, yi);
ll lower = ceil(-1.0 * n * xi / t2);
ll up = floor(1.0 * n * yi / t1);
if (lower > up || n % d) {
printf("failed\n");
continue;
}
if (c1 * t2 > c2 * t1) {
x = xi * n / d + t2 / d * lower;
y = yi * n / d - t1 / d * lower;
} else {
x = xi * n / d + t2 / d * up;
y = yi * n / d - t1 / d * up;
}
printf("%lld %lld\n", x, y);
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。