P15288 「YLLOI-R3-T3」龙卷风

题目描述

给定 $n$ 个正整数和一个正整数 $m$，求对于所有 $k\in [1,m]$，存在多少个正整数 $k$ 满足：

任意排列这 $n$ 个数并把他们放入一个长度为 $n$ 的环里可能使得该环中任意连续的 $k$ 个元素的和相等。

输入格式

本题有多组测试数据。

第一行一个整数 $T$，表示数据组数。

对于每组数据：

第一行两个正整数 $n,m$。

第二行 $n$ 个正整数 $a_i$。

输出格式

对于每组数据：

一行一个整数。

输入输出样例 #1

输入 #1

1
2
31
5 4
1 2 1 2 1

输出 #1

10

输入输出样例 #2

输入 #2

1
2
31
6 5
1 1 2 2 2 2

输出 #2

11

说明/提示

【样例解释#1】

可以证明，对于任何一个整数 $k\in [1,4]$，都无法使得满足题意。

【样例解释#2】

当且仅当 $k=3$ 时可以构造出一组满足题意的方案：$[1,2,2,1,2,2]$。

此时连续的 $k$ 个元素的和恒为 $5$。

【数据范围】

本题采用捆绑测试。

• Subtask 1（10 pts）：$m\le 1$。
• Subtask 2（20 pts）：$m\le 2$。
• Subtask 3（20 pts）：$n$ 为质数。
• Subtask 4（10 pts）：$a_i$ 互不相同。
• Subtask 5（20 pts）：$n\le 100$。
• Subtask 6（20 pts）：无特殊限制。

对于全部数据，保证：$1\le T\le 100$，$1\le m\le n\le 10^4$，$1\le a_i\le 10^9$。