Acwing199 余数之和

原题面：https://www.acwing.com/problem/content/201/

题目大意：给出正整数n和k，计算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值。例如j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7。

输入描述：输入仅一行，包含两个整数n, k。

输出描述：输出仅一行，即j(n, k)。

输入样例：

5 3

输出样例：

7                            

分析：k%i=k-[k/i]i，所以原式可以化简为nk-(1<=i<=n)[k/i]*i。反正最后划来划去可以得到[x,[k/[k/x]]]区间内，[k/i]的值都相等。最后就是多个等差数列求和的问题。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll n, k;
    scanf("%lld%lld", &n, &k);
    ll ans = n * k;
    for (int x = 1, gx; x <= n; x = gx + 1) {
        gx = k / x ? min(k / (k / x), n) : n;
        //[x,[k/[k/x]]]
        ans -= (k / x) * (x + gx) * (gx - x + 1) / 2;//第一项为(k/x)*x*(gx-x+1),最后一项为(k/x)*gx*(gx-x+1)，此为一个等差数列区间
    }
    cout << ans << endl;
    return 0;
}