题意分析

题目描述了一个老虎机的游戏机制，每个老虎机由$w$个转轮组成，每个转轮的头奖符号出现的周期为$p_k$。老虎机出厂时显示头奖组合，之后每次运行游戏，转轮会按照各自的周期循环显示符号。我们需要计算老虎机在两次头奖组合之间需要运行的游戏次数，即所有转轮周期的最小公倍数（LCM）。

解题思路

• 问题转化：头奖组合出现的条件是所有转轮同时显示头奖符号，因此需要计算所有转轮周期$p_1, p_2, \ldots, p_w$的最小公倍数。
• 数学基础：两个数$a$和$b$的最小公倍数可以通过公式$\text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)}$计算，其中$\text{GCD}(a, b)$是$a$和$b$的最大公约数。
• 扩展性：对于多个数的最小公倍数，可以依次计算前两个数的LCM，再将结果与下一个数计算LCM，直到所有数处理完毕。

实现步骤

1. 输入处理：读取机器数量$n$，然后对于每台机器，读取转轮数量$w$和周期数组$p$。
2. 计算LCM：初始化LCM为第一个周期，然后依次与其他周期计算LCM。
3. 结果判断：如果最终LCM不超过$10^9$，输出结果；否则输出"More than a billion."。

C++实现

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

int main() {
    int t, n;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        long long a, b;
        scanf("%lld", &a);
        for (int i = 1; i < n; i++) {
            scanf("%lld", &b);
            a = lcm(a, b);
        }
        if (a <= 1000000000)
            printf("%lld\n", a);
        else
            printf("More than a billion.\n");
    }
    return 0;
}

代码说明

• 函数gcd：使用欧几里得算法递归计算两个数的最大公约数，时间复杂度为$O(\log(\min(a, b)))$。
• 函数lcm：利用公式$\text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)}$计算最小公倍数，避免直接相乘可能导致的溢出问题。
• 主函数：
  • 读取机器数量$t$。
  • 对于每台机器，读取转轮数量$n$和周期数组，初始化$a$为第一个周期。
  • 依次计算$a$与后续周期的LCM，更新$a$。
  • 判断$a$是否超过$10^9$，输出相应结果。