CF773F Test Data Generation

生成测试数据并非易事！通常，仅仅生成大量的随机测试用例并不足以确保对解答的充分正确性测试。 例如，考虑某次旧 Codeforces 比赛中的一道题。其输入格式大致如下： 第一行为一个整数 $n$（$1 \leq n \leq max_{n}$），表示集合的大小。第二行为 $n$ 个互不相同的整数 $a_1, a_2, ..., a_n$（$1 \leq a_i \leq max_{a}$），这些数以递增顺序排列，表示集合中的元素。 如果你不考虑该题的解法，表面上看生成此类题目的测试点非常容易。令 $n = max_{n}$，从 $1$ 到 $max_{a}$ 间随机选取 $n$ 个不同的 $a_i$，然后将它们排序……很快你就会发现，实际上没那么简单。 来看题目的实际解法。令 $g$ 为 $a_1, a_2, ..., a_n$ 的最大公约数。令 $x = a_n / g - n$。若 $x$ 为奇数，输出 "Alice"；若 $x$ 为偶数，输出 "Bob"。 考虑两种错误解法，它们只是在求 $x$ 的公式上与标准解略有不同。 第一种错误解法计算 $x = a_n / g$（没有减去 $n$）。 第二种错误解法计算 $x = a_n - n$（没有除以 $g$）。 如果一个测试用例能让上述两种错误解法都输出错误答案，则称该测试用例为有趣的测试用例。 给定 $max_n$、$max_a$ 和 $q$，请找出满足约束条件的有趣测试用例个数，并对 $q$ 取模后输出。

仅一行，包含三个整数 $max_n$、$max_a$ 和 $q$（$1 \leq max_n \leq 30000$；$max_n \leq max_a \leq 10^9$；$10^4 \leq q \leq 10^5+129$）。

输出一个整数，即满足题意的有趣测试用例数，对 $q$ 取模后的结果。

在第一个示例中，有趣的测试用例如下： `

1 1 1 3

2 4 6 2 4 6

` 由 ChatGPT 5 翻译