AT4873 [ABC139D] ModSum 题解

qjxqjx · 2022-01-27 17:18:06 · 题解

题目大意：

有一个数组 a，且 a_i=i，求将数组排列后 a_i \bmod i 后的最大值。

题目思路：

超级水题。首先可以发现一个数取模之后，所得数必定会小于取模的数，所以让一个数取模的结果尽可能的大，就要找一个比数本身还大的数作为模数，那么我们就把每个数向前移动一个单位，也就是，易得 i-1 \bmod i =i-1。向后枚举，可得结果为等差数列求和,套公式即可：

注意：数据原因开 long long

代码：

#include<bits/stdc++.h>
using namespace std;
long long n;//千万要开long long
int main(){
    cin>>n;
    cout<<n*(n-1)/2;//套公式输出
    return 0;
}