单点时限: 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:
等),然后在一行中输出不同最简真分数的个数。
3 5 1 2 30 2 3 3 1000 1000 1000 7 3 5 7 15 13 11 9
case #0: 4 case #1: 0 case #2: 17