UPC11449 余数求和（分块）

时间限制: 1 Sec  内存限制: 128 MB
提交: 91  解决: 48
[提交] [状态] [命题人:admin]

题目描述

给出正整数n和k，计算j(n,k)=k mod 1 + k mod 2 + k mod 3 +⋯+ k mod n的值。其中
k mod i表示k除以i的余数。

例如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（1≤n,k≤109）。

输出

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

样例输入

复制样例数据

5 3

样例输出

7

来源/分类

提高 

 

对于给定正整数i和n满足$ i leq n$,使得$lfloor frac{n}{i} floor = lfloor frac{n}{x} floor$成立的最大的x为$frac{n}{lfloor frac{n}{i} floor}$

$k \% i =k- lfloor frac{k}{i} floor imes i$ ，利用分块及等差数列求和公式快速求解

 

#include "bits/stdc++.h"

using namespace std;
typedef long long ll;

int main() {
    //freopen("input.txt", "r", stdin);
    ll n, k;
    ll ans = 0;
    cin >> n >> k;
    for (ll i = 1, j; i <= n; i = j + 1) {
        ll t = k / i;
        if (!t) j = n;
        else j = k / t;
        j = min(j, n);
        ll len = j - i + 1;
        ans = ans + k * len - (t * i + t * j) * len / 2;
    }
    cout << ans << endl;
    return 0;
}