乘法表 - 题目

Peter 昨天在学校学习了乘法。他对此感到非常兴奋，以至于熬夜写出了一个非常大的乘法表，如下所示：

1 2 3 4 5 6 7 8 9 10 ··· 2 4 6 8 10 12 14 16 18 20 ··· 3 6 9 12 15 18 21 24 27 30 ··· 4 8 12 16 20 24 28 32 36 40 ··· 5 10 ··· 6 12 ··· 7 14 ··· ···

该表中第 $i$ 行第 $j$ 列的值为 $i \times j$（假设行和列均从 1 开始索引）。你可以假设该表有无限多的行和列。

昨晚，Peter 即使在睡着后，也一直在梦中想着这张表。他觉得自己看到了表的一部分，是一个 $R$ 行 $C$ 列的矩形。（Peter 的矩形不一定从第一行或第一列开始，但其方向与乘法表一致。）醒来后，他写下了整个矩形，并用“?”表示他不记得的数字。

现在，Peter 想知道他梦中的这个数字矩形是否真的可能存在于乘法表中。你能帮他判断吗？

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。

每个测试用例的第一行包含两个数字 $R$ 和 $C$，即 Peter 矩形的行数和列数。

接下来有 $R$ 行，每行包含 $C$ 个以空格分隔的值，每个值要么是一个数字，要么是“?”。“?”表示 Peter 不记得该单元格中的数字。

对于每个测试用例，输出一行“Case #x: y”，其中 $x$ 是测试用例编号（从 1 开始），如果该矩形能匹配乘法表的一部分，则 $y$ 为“Yes”，否则为“No”。

5
3 3
4 ? 8
? 9 ?
? ? ?
3 4
? ? ? ?
? ? ? ?
3 6 8 12
1 2
1000000000 ?
1 2
? 1
2 1
?
?

Case #1: Yes
Case #2: No
Case #3: Yes
Case #4: No
Case #5: Yes

在样例 1 中，该矩形可以匹配从乘法表第二行第二列开始的部分：

4 6 8 6 9 12 8 12 16

在样例 2 中，该矩形不可能匹配乘法表的一部分。（特别地，乘法表中没有任何一行包含连续的 3, 6, 8, 12。）

注意在样例 3 中，未知值必须大于 $10^9$（例如，它可以是 $2 \times 10^9$）。$10^9$ 的限制仅针对 Peter 记得的数字。

在样例 4 中，乘法表中没有任何值可以出现在 1 之前。

QOJ.ac