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;
}