宁波市第29届中小学生程序设计竞赛复赛试题 初中组

4. 马球比赛 (polo.pas/c/cpp)

【问题描述】

在解决了马语翻译问题后，马匹数量越来越多，不少乡镇都有了数量可观的马匹，开始出现马球比赛。乡镇之间决定进行马球联赛。

联赛的赛制，主要是比赛双方的马匹数量，成了一个急需解决的问题。首先，所有乡镇都要求，本乡镇所有的马匹都必须参赛，或者都不参赛（若组队的马匹数量不是该镇马匹数量的约数，将无法参赛）。其次，在本乡镇，选出最佳球队，参加乡镇间联赛。

现在，比赛组织方希望满足所有参赛乡镇的要求，并且使得决赛的马匹尽可能多，请你设计每个球队马匹的数量，使得决赛马匹数最大。注意，决赛至少有2个队伍晋级。

【输入】

第一行一个整数N，表示想要报名参赛的乡镇。

接下来N个用空格分开的整数a(i)，表示第i个乡镇报名参赛的马匹数。

【输出】

计算出决赛最大参与的马匹数。

【输出输出样例1】 polo.in polo.out 3 1 3 6 6 【样例解释】 每个队伍3匹马，乡镇1无法参赛。乡镇2和3都可以进行比赛，决赛2个队伍，共6匹马。

【输出输出样例2】 polo.in polo.out 2 1 3 2 【样例解释】 每个队伍1匹马，因为至少需要2个队伍晋级。 【输出输出样例3】 polo.in polo.out 5 4 6 3 8 9 9 【样例解释】

每个队伍3匹马，乡镇2,3,5可以参赛。决赛3个队伍，9匹马。 【数据范围】

20%的数据2<=N<=100，1<=a(i)<=10000。 50%的数据2<=N<=20000。

100%的数据2<=N<=200000，1<=a(i)<= 2000000。

第 5 页 共 5 页