bzoj#P4210. 香果屋
香果屋
题目描述
「即使执政官再圆,也不是我子民的样子!」——西瓜王
xgw 为了见到真正的西瓜,来到了小镇著名的水果店「香果屋」。他在这里看到了很多又大又圆的西瓜,他决定带几个西瓜回家。「香果屋」里有 种西瓜,每种西瓜有一个权值 ,而有钱任性的 xgw 把每种西瓜都买了一个带回家!!
将西瓜带回家后,xgw 自然是要向他们的子民训话。每次他会从中选出一个子集进行训话,每次训话的愉悦度是选出西瓜的权值的最小公倍数乘最大公约数。
他是个任性的国王,他会把每种可以选择的方式都来一遍,当然,每次选择至少选出一个西瓜(也就是不会为空集)。
你需要求的是 xgw 训话完之后的愉悦值之和。由于答案可能过大,请输答案 的值。
输入格式
本题有多组数据。
第一行包含一个整数 , 代表测试数据的组数。
接下来是 组测试数据,对每一组测试数据:
第一行包含一个整数 , 代表元素的个数。
第二行包含 个用空格隔开的互不相同的正整数 。
输出格式
对每组测试数据,在新的一行输出答案。
样例
2
2
2 3
3
2 4 10
19
228
样例说明
第一组数据:
子集 :$\{2\} \rightarrow lcm = 2, gcd = 2, lcm\times gcd = 4$
子集 :$\{3\} \rightarrow lcm = 3, gcd = 3, lcm\times gcd = 9$
子集 :$\{2,3\} \rightarrow lcm = 6, gcd = 1, lcm\times gcd = 6$
第二组数据:
子集 :$\{2\} \rightarrow lcm = 2, gcd = 2, lcm\times gcd = 4$
子集 :$\{4\} \rightarrow lcm = 4, gcd = 4, lcm\times gcd = 16$
子集 :$\{10\} \rightarrow lcm = 10,gcd = 10 , lcm\times gcd = 100$
子集 :$\{2,4\} \rightarrow lcm = 4, gcd = 2 , lcm\times gcd = 8$
子集 :$\{4,10\} \rightarrow lcm = 20,gcd = 2 , lcm\times gcd = 40$
子集 :$\{2,10\} \rightarrow lcm = 10,gcd = 2 , lcm\times gcd = 20$
子集 :$\{2,4,10\} \rightarrow lcm = 20,gcd = 2 , lcm\times gcd = 40$
数据规模与约定
对于 的数据:,,。