测试数据生成并不是一件容易的事!通常,生成大量随机测试用例不足以确保彻底测试解决方案的正确性。
例如,考虑旧 Codeforces 回合中的问题。其输入格式大致如下:
第一行包含一个整数 n (1 ≤ n ≤ maxn) — 集合的大小。第二行包含 n 个不同的整数 a1, a2, ..., an (1 ≤ ai ≤ maxa) - 集合中的元素按升序排列。
如果您不注意问题的解决方案,那么为这个问题生成一个好的测试用例看起来相当容易。让n = maxn,从1到maxa中随机取不同的ai,对它们进行排序......很快你就会明白这并不那么容易。
这是实际的问题解决方案。令 g 为 a1, a2, ..., an 的最大公约数。设 x = an / g - n。如果 x 是奇数,则正确的解决方案输出“Alice”,如果 x 是偶数,则正确的解决方案输出“Bob”。
考虑该问题的两种错误解决方案,它们与正确解决方案的不同之处仅在于计算 x 的公式。
第一个错误的解决方案将 x 计算为 x = an / g(不减去 n)。
第二个错误的解决方案将 x 计算为 x = an - n(不除以 g)。
如果测试用例使两个错误的解决方案都输出错误的答案,则该测试用例很有趣。
给定 maxn、maxa 和 q,找到满足约束的有趣测试用例的数量,并以 q 为模输出。
输入
唯一一行包含三个整数 maxn、maxa 和 q (1 ≤ maxn ≤ 30 000;maxn ≤ maxa ≤ 109;104 ≤ q ≤ 105 + 129)。
输出
输出一个整数——满足约束条件并使两个错误的解决方案都输出错误答案的测试用例的数量,以 q 为模。
示例
输入 #1
3 6 100000
输出 #1
4
输入 #2
6 21 100129
输出 #2
154
输入 #3
58 787788 50216
输出 #3
46009
注意
在第一个示例中,有趣的测试用例如下所示: