bzoj#P4210. 香果屋

香果屋

题目描述

「即使执政官再圆,也不是我子民的样子!」——西瓜王

xgw 为了见到真正的西瓜,来到了小镇著名的水果店「香果屋」。他在这里看到了很多又大又圆的西瓜,他决定带几个西瓜回家。「香果屋」里有 nn 种西瓜,每种西瓜有一个权值 xix_i,而有钱任性的 xgw 把每种西瓜都买了一个带回家!!

将西瓜带回家后,xgw 自然是要向他们的子民训话。每次他会从中选出一个子集进行训话,每次训话的愉悦度是选出西瓜的权值的最小公倍数乘最大公约数。

他是个任性的国王,他会把每种可以选择的方式都来一遍,当然,每次选择至少选出一个西瓜(也就是不会为空集)。

你需要求的是 xgw 训话完之后的愉悦值之和。由于答案可能过大,请输答案 ansmod105ans\mod 10^5 的值。

输入格式

本题有多组数据

第一行包含一个整数 TT, 代表测试数据的组数。

接下来是 TT 组测试数据,对每一组测试数据:

第一行包含一个整数 nn, 代表元素的个数。

第二行包含 nn 个用空格隔开的互不相同的正整数 xix_i

输出格式

对每组测试数据,在新的一行输出答案。

样例

2
2
2 3
3
2 4 10
19
228

样例说明

第一组数据:

子集 11:$\{2\} \rightarrow lcm = 2, gcd = 2, lcm\times gcd = 4$

子集 22:$\{3\} \rightarrow lcm = 3, gcd = 3, lcm\times gcd = 9$

子集 33:$\{2,3\} \rightarrow lcm = 6, gcd = 1, lcm\times gcd = 6$

ans=4+9+6=19ans = 4 + 9 + 6 = 19

第二组数据:

子集 11:$\{2\} \rightarrow lcm = 2, gcd = 2, lcm\times gcd = 4$

子集 22:$\{4\} \rightarrow lcm = 4, gcd = 4, lcm\times gcd = 16$

子集 33:$\{10\} \rightarrow lcm = 10,gcd = 10 , lcm\times gcd = 100$

子集 44:$\{2,4\} \rightarrow lcm = 4, gcd = 2 , lcm\times gcd = 8$

子集 55:$\{4,10\} \rightarrow lcm = 20,gcd = 2 , lcm\times gcd = 40$

子集 66:$\{2,10\} \rightarrow lcm = 10,gcd = 2 , lcm\times gcd = 20$

子集 77:$\{2,4,10\} \rightarrow lcm = 20,gcd = 2 , lcm\times gcd = 40$

ans=4+16+100+8+40+20+40=228ans = 4 + 16 + 100 + 8 + 40 + 20 + 40 = 228

数据规模与约定

对于 100%100\% 的数据:1T4001\le T\le 4002n1002\le n\le 1001xi2501\le x_i\le 250