题解：CF2110F Faculty
lw393
·
·
题解
这道题算是本场除 AB 外，代码最为简单的了，但是思维难度大。
我们先证明命题 1：f(x,y) \le \max(x,y)
证明：
若 x = y 则 f(x,y) = 0。
否则设 x \le y。
此时 x \bmod y = x, y \bmod x = y -\lfloor\frac yx\rfloor x。
由于 $\lfloor\frac yx\rfloor \ge 1$，命题得证。
再证明命题 $2$：长度为 $k$ 的前缀中最大的 $f(a_i,a_j)$，$a_i \ge a_j$，在 $a_i = \max_{j=1}^k a_j$ 中取得。
证明：
设 $a_i$ 为长度为 $k$ 的前缀中的最大元素，$f(a_x, a_y)$ 大于找到的值，$a_x \le x_y$，由前命题，得 $f(a_x, a_y)\le a_y$。
我们再考虑 $f(a_i, a_y)$，由于 $a_y \le a_i$，得 $f(a_x,a_y)\le a_y \le f(a_i,a_y)$。
最后证明命题三：若 $x < y < 2x$，则 $f(x,y) = y
证明：
借助上述三个命题得正确性，我们可以枚举了。设在长度为 $k$ 的前缀中，最大值为 $x$，最大的 $f(x,y)$ 为 $ans$。
我们用以下步骤更新 $ans$：
1. 若 $a_{k+1} <x$，利用命题 $2$，更新 $ans$；
2. 若 $x < a_{k+1} < 2x$，利用命题 $3$，更新 $ans$；
3. 若 $a_{k+1} \ge 2x$，直接暴力遍历数组。
由于每次在前缀最大值达到前一个最大值的两倍才会枚举数组内的所有元素，所以时间复杂度可以证明是 $O(n\log A)$，其中 $A = \max_{i=1}^n a_i$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int f(int x, int y) { return x % y + y % x; }
void solve(){
int n; cin >> n;
vector<int>a(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
int ans = 0, maxn = a[1];
for(int i = 1; i <= n; i++){
ans = max(ans, f(maxn, a[i]));
if(a[i] > maxn){
if(a[i] >= maxn * 2){
maxn = a[i];
for(int j = 1; j <= i; j++) ans = max(ans, f(a[i], a[j]));
} else { maxn = a[i]; ans = maxn; }
}
cout << ans << ' ';
}
cout << '\n';
}
int main(){
int t = 1;
cin >> t;
while(t--){
solve();
}
return 0;
}
```