2957. 统计不同的最简真分数的个数

单点时限: 2.0 sec

内存限制: 256 MB

任取 N 个正整数中的两个数作为分子和分母组成的分数中有一部分是最简真分数。编程计算不同最简真分数的个数。

例如:5 个数 1,2,30,2,3 组成的不同最简真分数包括$\frac{1}{2}, \frac{1}{30}, \frac{1}{3}, \frac{2}{3}$共 4 个。

输入格式

第 1 行:整数 $T$ ($1 \le T \le 10$) 为问题数

第 2 行:第 1 个问题的整数 $N (2\leqslant N \leqslant 1000)$

第 3 行:第 1 个问题的 N 个数据 $a_i(1 \leqslant a_i \leqslant 1000)$ , 数据之间由一个空格分隔。

后面是第 2 ∽ T 个问题的数据。格式与第 1 个问题相同。

输出格式

对于每个问题,输出一行问题的编号(0 开始编号,格式:case #0: 等),然后在一行中输出不同最简真分数的个数。

样例

Input
3
5
1 2 30 2 3
3
1000 1000 1000
7
3 5 7 15 13 11 9
Output
case #0:
4
case #1:
0
case #2:
17

522 人解决,566 人已尝试。

777 份提交通过,共有 1810 份提交。

1.2 EMB 奖励。

创建: 8 年,3 月前.

修改: 2 年前.

最后提交: 4 天,22 小时前.

来源: 2012年程序设计实践第8次上机考试

题目标签
DP