求多个数的最小公倍数,水题。题意:简单说吧,老虎机有几个转盘,每一个转盘停留在jackpot上都有一个固定的周期,如果所有转盘都停留在jackpot上,那么就可以赢钱,现在要求赢钱的周期,如果大于指定的数就要给出指定的信息。
我的解题思路:每个转盘的周期求最小公倍数就可以了,考虑一下边界情况只有一个转盘的情况就行了,另外根据题意如果最小公倍数大于10^9的话就输出“More than a billion.”就好了。
我的解题代码:
#include <stdio.h> #include <cstdlib> #include <cstring> #include <cctype> #include <cmath> #include <algorithm> using namespace std; typedef long long Long; const Long N = 5; const Long M = 10e9; Long num[N]; Long ans; int t, n; Long Gcd(Long a, Long b); Long Lcm(Long a, Long b); int main() { scanf("%d", &t); while (t--) { scanf("%d", &n); for (int i=0; i<n; ++i) { scanf("%lld", &num[i]); } ans = num[0]; for (int i=1; i<n; ++i) ans = Lcm(ans, num[i]); if (ans <= M) printf("%lld\n", ans); else puts("More than a billion."); } return 0; } Long Gcd(Long a, Long b) { return b == 0 ? a : Gcd(b, a % b); } Long Lcm(Long a, Long b) { return a / Gcd(a, b) * b; }