Preparing NOJ

演唱顺序问题II

1000ms 65536K

Description:

 2014“华为杯南京邮电大学大学生团体歌唱大赛与2013年情况相似:大赛分为多轮,每一轮随机选择参赛团体进行两两PK赛。当根据多轮多场的PK赛成绩能够确定排名次序时,大赛结束。但对于去年的PK赛,有些参赛选手颇有微词,认为PK赛演唱顺序虽然通过抽签来公平决定,但是不能充分展示南邮作为中国IT精英摇篮的风采,建议2014PK赛演唱顺序通过脑力决定,例如搞些智力抢答,最快回答正确的参赛团队优先决定自己的演唱顺序。

主办方认为PK赛演唱顺序通过脑力决定的想法值得尝试,于是决定在2014“华为杯歌唱大赛采用以下方案:主办方给参加PK赛的两个团队一系列正整数,请每一个团队按照规则进行变换,直至认为上述一系列正整数之和为最小,最快获得正确结果的团队优先决定自己的演唱顺序,其中变换规则描述如下:在给定的一系列正整数中,任取两个正整数AB,如果A>B,则可以将A变为A-B,也就说A=A-B,这些变换可以进行任意次。举例说明,若给定正整数分别为24816,则经过变换后,求得的最小之和为8。我依然对主办方采用的上述方案感到困惑,想知道进行任意次变换后求得的最小之和是多少,请你帮助解决这个问题。


Input:

输入包括多个测试用例,首先给出测试用例数N,接着给出N个测试用例,每一个测试用例包括1行,首先给出正整数序列数M,接着依次给出M个正整数,1≤N≤1000002≤M≤500000,正整数大小不超过1000


Output:

针对每一个测试用例,输出一行,给出对一系列正整数进行任意次变换后求得的最小之和。


Sample Input:

2
4 2 4 8 16
3 3 2 2

Sample Output:

8
3

Note:

本题由旧版NOJ导入,来源:SED

Info

NOJ

Provider NOJ

Code NOJ2041

Tags

Submitted 1

Passed 1

AC Rate 100%

Date 04/20/2019 10:03:10

Related

Nothing Yet