首页 > 代码库 > UVA10717 - Mint(欧几里德求最小共倍数)
UVA10717 - Mint(欧几里德求最小共倍数)
UVA10717 - Mint(欧几里德求最小共倍数)
题目链接
题目大意:要求你设计桌子,桌子的四条腿是用四种不同的硬币堆砌起来,并且这四条腿的长度要求要种相同。现在给n种硬币,然后给你t个要求的高度H。要求你给出能够用这些硬币设计出来的桌子的高度最接近H的两个数。
解题思路:要求四条腿一样长的话就是求这四种硬币厚度的最小共倍数,然后这里会给n种硬币,需要枚举出每四个的组合,求出用这些硬币可以设计多高的桌子。最后再根据题目要求的高度将这些可以得到的桌子高度进行安放。
代码:
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 50;
const ll INF = 0x3f3f3f3f;
int k, t;
ll num[maxn], H[maxn];
ll L[maxn], R[maxn];
ll gcd (ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
void init () {
for (int i = 0; i < k; i++)
scanf ("%lld", &num[i]);
for (int i = 0; i < t; i++)
scanf ("%lld", &H[i]);
for (int i = 0; i < t; i++) {
L[i] = 0;
R[i] = INF;
}
}
void solve (ll a) {
ll tmp;
for (int i = 0; i < t; i++) {
tmp = a;
while (1) {
if (tmp == H[i]) {
L[i] = max(L[i], tmp);
R[i] = min(R[i], tmp);
break;
} else if (tmp < H[i]) {
L[i] = max(L[i], tmp);
} else {
L[i] = max(L[i], tmp - a);
R[i] = min(R[i], tmp);
break;
}
tmp += a;
}
}
}
int main () {
while (scanf ("%d%d", &k, &t) && (k || t)) {
init();
ll tmp1, tmp2, tmp;
for (int i = 0; i < k; i++)
for (int j = i + 1; j < k; j++) {
tmp1 = num[i] / gcd(num[i], num[j]) * num[j];//先除再乘防止溢出
for (int m = j + 1; m < k; m++)
for (int n = m + 1; n < k; n++) {
tmp2 = num[m] / gcd(num[m], num[n]) * num[n];
tmp = tmp1 / gcd(tmp1, tmp2) * tmp2;
solve(tmp);
}
}
for (int i = 0; i < t; i++)
printf ("%lld %lld\n", L[i], R[i]);
}
return 0;
}
UVA10717 - Mint(欧几里德求最小共倍数)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。