#P5728. [省选联考 2021 B 卷] 取模

    ID: 4729 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 7 上传者: 标签>难度分类提高+/省选-排序与序列处理排序后去重枚举枚举与搜索最优性剪枝相向双指针数论同余的加减乘运算CF2200

[省选联考 2021 B 卷] 取模

题目描述

给定 nn 个正整数 aia_i,请你在其中选出三个下标 i,j,ki,j,k(i≠ji \ne j,i≠ki \ne k,j≠kj \ne k),使得 (ai+aj) mod ak(a_i + a_j) \bmod a_k 的值最大。

输入格式

第一行,一个整数 nn,表示数字个数。
第二行,nn 个整数,表示 aia_i。

输出格式

输出一行,一个整数,表示答案。

样例 #1

6
4 7 7 5 2 2
6

提示

补充样例 #2

3
6 8 9
7

选择 ai=6,aj=9,ak=8a_i=6,a_j=9,a_k=8,得到 15 mod 8=715\bmod 8=7。

数据范围

对于 30%30 \% 的数据,n≤100n \le 100。
对于 60%60 \% 的数据,n≤3000n \le 3000。
对于 100%100 \% 的数据,3≤n≤2×1053 \le n \le 2 \times {10}^5,1≤ai≤1081 \le a_i \le {10}^8。

原题面 PDF