UOJ Logo Universal Online Judge

UOJ

#979. 【UR #31】决战库尔斯克

附件下载 统计

English Problem Statement

作为苏军近卫装甲集团军的指挥官,你受命延加里宁—捷捷列维诺一线对冒进的德军侧翼发起反击。

敌军把守住了 $n$ 个关键据点,呈现出“一”字形的防守态势,其中第 $i$ 个据点有地形值 $a_i$。

你决定选择两个据点进行进攻——一个作为主攻方向,一个作为辅攻方向,以形成钳形攻势。由于地形值越高越易攻难守,你会选择两个据点中地形值较大的一个作为主攻方向,若相同则随机选择。

经过你的参谋部的细致调查研究,你发现一个进攻计划的作战效果等于主攻方向地形值对辅攻方向地形值取余数后的结果。

现在,你需要编写一个程序求出所有进攻计划中作战效果的最大值。由于德国人布置了多层防御,你可能还需要对多组数据分别求出答案。联盟与全人类的命运此刻由你决定,祝你好运,同志。

形式化题意: 给定正整数数组 $a_1, a_2, \cdots, a_n$,你需要选出两个不同的下标 $1 \leq i,j \leq n$,最大化 $\max(a_i,a_j) \bmod \min(a_i,a_j)$ 的值。

输入格式

本题单个测试点内有多组数据。

第一行仅包含一个整数 $T$,表示数据组数。对于每组数据:

  • 第一行包含一个整数 $n$。
  • 第二行包含 $n$ 个正整数 $a_1, a_2, \cdots, a_n$。

输出格式

对于每组数据,输出仅一行一个整数,表示作战效果的最大值。

样例一

input

2
5
1 2 3 4 5
10
1 67 11 49 103 527 44 61 138 113

output

2
113

explanation

对于第一组数据,选取据点 $3$ 和据点 $5$,地形值分别为 $3$ 和 $5$,作战效果等于 $5 \bmod 3 = 2$,可以证明,不存在比该方案的作战效果更大的方案。

对于第二组数据,选取据点 $6$ 和据点 $9$,地形值分别为 $527$ 和 $138$,作战效果等于 $527 \bmod 138 = 113$,可以证明,不存在比该方案的作战效果更大的方案。

样例二、三

见附件下载。

限制与约定

本题采用捆绑测试,各个子任务之间开启所有合理的子任务依赖。

设单个测试点中每组数据的 $n$ 的和为 $\sum n$。对于所有数据,保证 $2 \leq n,\sum n \leq 5 \cdot 10^5$,$1 \leq a_i \leq 10^{18}$。

  • Subtask 1(10 points):保证 $\sum n \leq 5000$;
  • Subtask 2(15 points):保证 $a_i \leq 10^6$;
  • Subtask 3(25 points):保证 $a_i$ 在 $[1,10^{18}]$ 中独立均匀随机生成,保证测试点个数最多为 $5$ 个;
  • Subtask 4(30 points):保证 $\sum n \leq 5 \cdot 10^4$;
  • Subtask 5(20 points):无额外约束。

时间限制: $\texttt{1s}$

空间限制: $\texttt{512MB}$