题目分析

题目要求

判断给定的 STEP 和 MOD 是否能使伪随机数生成函数
[ \text{seed}(x+1) = (\text{seed}(x) + \text{STEP}) % \text{MOD} ]
在 MOD 次迭代内生成 0 到 MOD-1 的所有整数。若能，输出“Good Choice”，否则输出“Bad Choice”。

关键结论

生成函数能覆盖所有值的充要条件是 STEP 和 MOD 互质（即它们的最大公约数 GCD(STEP, MOD) = 1）。

• 互质：当且仅当两个数的最大公约数为 1 时，序列的周期为 MOD，每个数恰好出现一次。
• 非互质：周期为 MOD / GCD(STEP, MOD)，生成的数仅有 MOD / GCD(STEP, MOD) 个，无法覆盖所有值。

代码思路

1. 输入处理：循环读取多组 STEP 和 MOD，直到文件结束（EOF）。
2. 最大公约数计算：使用 欧几里得算法（辗转相除法）计算两数的 GCD。
3. 结果判断：根据 GCD 是否为 1 输出相应结果。

代码解析

1. 主函数逻辑

int main() {
    long step, mod;
    while (scanf("%ld%ld", &step, &mod) != EOF) { // 循环读取输入
        if (gcd(step, mod) == 1) 
            printf("%10d%10d    Good Choice\n\n", step, mod); // 互质时输出好选择
        else 
            printf("%10d%10d    Bad Choice\n\n", step, mod); // 否则输出坏选择
    }
    return 0;
}

• 输入处理：scanf 返回成功读取的参数个数，EOF 通常对应输入结束（如 Ctrl+D 或文件末尾）。
• 格式化输出：
  • %10d：右对齐，占 10 列，不足补空格。
  • \n\n：每个结果后输出两个换行符（题目要求“输出后打印一个空行”，此处第二个 \n 实现空行）。

2. 欧几里得算法（GCD 计算）

long gcd(long a, long b) {
    long c;
    if (b == 0) return a; // 递归终止条件：余数为 0 时，除数即为 GCD
    c = a % b;
    while (c) { // 当余数不为 0 时，继续迭代
        a = b;
        b = c;
        c = a % b;
    }
    return b; // 最终除数为 GCD
}

• 算法原理：
  • 若 b = 0，返回 a（GCD 定义）。
  • 否则，用较大数除以较小数，将除数作为新的被除数，余数作为新的除数，重复此过程直到余数为 0。

示例验证

输入：3 5

• GCD(3, 5) = 1 → 输出“Good Choice”。

输入：15 20

• GCD(15, 20) = 5 → 输出“Bad Choice”。

输入：63923 99999

• 计算 GCD(63923, 99999)：
  • 99999 ÷ 63923 = 1 余 36076
  • 63923 ÷ 36076 = 1 余 27847
  • 36076 ÷ 27847 = 1 余 8229
  • 27847 ÷ 8229 = 3 余 3160
  • 8229 ÷ 3160 = 2 余 1909
  • 3160 ÷ 1909 = 1 余 1251
  • 1909 ÷ 1251 = 1 余 658
  • 1251 ÷ 658 = 1 余 593
  • 658 ÷ 593 = 1 余 65
  • 593 ÷ 65 = 9 余 8
  • 65 ÷ 8 = 8 余 1
  • 8 ÷ 1 = 8 余 0 → GCD = 1 → 输出“Good Choice”。

复杂度分析

• 时间复杂度：欧几里得算法的时间复杂度为 (O(\log \min(a, b)))，对于题目给定的数值范围（≤1e5），计算速度极快。
• 空间复杂度：仅使用常数级变量，空间复杂度为 (O(1))。

注意事项

1. 数据类型：使用 long 类型确保能处理题目给定的最大值（1e5）。
2. 输出格式：严格按照右对齐和空格要求，避免格式错误。
3. 空行处理：每个输出后必须包含一个空行，通过 printf("\n\n") 实现（第一个 \n 为结果换行，第二个为空行）。