C-小菲爱数数_中国石油大学（北京）第三届“骏码杯”程序设计竞赛（同步赛）

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小菲刚刚学完质数,所以她很喜欢计算一个整数有多少个质因子.每当小菲看到一些整数,她都会很快计算出这些数字的最小公倍数,然后数出最小公倍数有多少个质因子.

但是大菲觉得这太简单了,她决定考验一下小菲,让小菲计算出一个数组所有子数组最小公倍数的质因子数目之和.

小菲觉得这个问题太难了,所以她想问问你.

正式地讲,给出一个长度为 $n$ 的数组 $a_1, a_2, a_3, \cdots, a_n$ ,请计算 $\sum\limits_{i = 1}^n\sum\limits_{j=i}^n f(\text{lcm}(a_{i \sim j}))$ ,其中 $f(x)$ 表示 $x$ 的质因子数目, $\text{lcm}(b)$ 表示数组 $b$ 中所有元素的最小公倍数, $a_{l \sim r}$ 表示 $a$ 中从 $l$ 到 $r$ 连续的一段子数组,即 $a_l, a_{l + 1}, a_{l + 2}, \cdots, a_r$ .

题目中出现的名词解释:

多个正整数共有的倍数被称为公倍数,其中最小公倍数指公倍数中除 $0$ 以外最小的数.例如 $6, 4$ 的最小公倍数为 $12$ ,因为不存在小于 $12$ 的正整数同时是 $4, 6$ 的倍数.

质数是指在大于 $1$ 的正整数中,除了 $1$ 和它本身以外不再有其他因数的正整数.一个数因子中的质数被称为该数的质因子.例如 $2, 3$ 是 $12$ 的质因子,但是 $1, 4, 5$ 不是,因为 $1, 4$ 不是质数, $5$ 不是 $12$ 的因子.

原数组中连续的一段区间内的元素组成的数组被称为原数组的子数组.例如 $[2], [2, 3], [1, 2, 3, 4]$ 是 $[1, 2, 3, 4]$ 的子数组,但是 $[1, 2, 4]$ 不是,因为不是连续的一段.

输入描述:

本题有多组测试数据.
第一行包含一行一个正整数,表示测试数据的数目,然后输入组独立的数据.

每组数据第一行输入一行一个正整数,表示数组的长度.

每组数据第二行输入以空格分隔的个正整数,表示输入的数组.

保证所有测试数据的之和不超过.

输出描述:

对于每个测试样例,输出一行一个非负整数表示答案.

示例1

输入

复制

1
3
4 6 3

输出

复制

说明

共有个子数组

 最小公倍数为,质因子有,共个.

 最小公倍数为,质因子有,共个.

 最小公倍数为,质因子有,共个.

 最小公倍数为,质因子有,共个.

 最小公倍数为,质因子有,共个.

 最小公倍数为,质因子有,共个.

答案为.