3340. 又是 GCD

单点时限: 2.0 sec

内存限制: 512 MB

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

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

输入格式

第一行两个整数

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

接下来有 组数据。每组数据 行:

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

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

测试点 子任务 矩阵元素
1
2, 3
4
5, 6
7
8
9, 10

输出格式

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

样例

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

提示

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

5 人解决,19 人已尝试。

6 份提交通过,共有 183 份提交。

8.8 EMB 奖励。

创建: 2 年,2 月前.

修改: 2 年,1 月前.

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

来源: 2017 直升研究生机试

题目标签