3340. 又是 GCD

单点时限: 2.0 sec

内存限制: 512 MB

先给出一个 $n$ 行 $m$ 列的矩阵,求一个连续子矩阵,使得子矩阵中的数的 GCD(最大公约数)大于 $1$。

问这个子矩阵(的元素个数)最大是多少?

输入格式

第一行两个整数 $q, t$ $(q \in {1,2}, 1 \leq t \leq 5)$。

其中 $q$ 是表示子任务 $1$ 或 $2$。关于子任务的详细说明参见数据规模。$t$ 是测试点数目。

接下来有 $t$ 组数据。每组数据 $n+1$ 行:

  • 第一行两个整数,分别为 $n,m$。
  • 接下来 $n$ 行每行 $m$ 个正整数,用空格隔开。

共有十个测试文件,规模约定如下(一个文件 $t$ 组数据全部答对才给分,每个文件分值相等):

测试点 子任务 $(q)$ $n,m$ 矩阵元素
1 $1$ $1 \leq n,m \leq 10$ $\leq 10^9$
2, 3 $1$ $1 \leq n,m \leq 40$ $\leq 10^9$
4 $1$ $1 \leq n,m \leq 100$ $\leq 10^9$
5, 6 $1$ $1 \leq n,m \leq 150$ $\leq 10^9$
7 $2$ $1 \leq n,m \leq 20$ $\leq 500$
8 $2$ $1 \leq n,m \leq 80$ $\leq 500$
9, 10 $2$ $1 \leq n,m \leq 500$ $\leq 500$

输出格式

对于每组数据,输出 Case x: yx 是从 1 开始的测试数据编号,y 是一个整数表示答案。如果没有解,输出 $0$。

样例

Input
1 1
3 3
2 6 8
4 8 3
6 9 4
Output
Case 1: 4

提示

输入规模较大,建议使用 scanf

6 人解决,27 人已尝试。

7 份提交通过,共有 228 份提交。

8.7 EMB 奖励。

创建: 7 年,1 月前.

修改: 7 年前.

最后提交: 7 月,1 周前.

来源: 2017 直升研究生机试

题目标签