Rockdu's Blog

题目背景

数学题，无背景

题目描述

给出正整数n和k，计算G(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值，其中k mod i表示k除以i的余数。例如G(10, 5)=5 mod 1 + 5 mod 2 + 5 mod 3 + 5 mod 4 + 5 mod 5 …… + 5 mod 10=0+1+2+1+0+5+5+5+5+5=29

输入输出格式

输入格式：

两个整数n k

输出格式：

答案

输入输出样例

10 5

29

说明

30%: n,k <= 1000

60%: n,k <= 10^6

100% n,k <= 10^9

首先可以手玩一组样例，其实可以很简单的发现规律：一个数的取模累加序列是由一段不规则区间和多段递减序列拼凑而成的：

例如25:
mod 1...25
0 1 1 1 0| 1/ 4 1/ 7 5 3 1/ 12 11 10 9 8 7 6 5 4 3 2 1 0/

不规则区间不好算，不过另一边比较好算。根据观察右边递减区间的公差在逐渐增大，首项取决于该项的mod是否整除原数。所以不规则区间的起始是可以通过等差数列的计算递推推导出来的——在根号内。我们暴力处理就好了。于是我们写一段代码：

#include<iostream>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std;
LL n, k, l, r, ans;
int i;
LL sigma(LL x1, LL dt, LL num) {
    LL xn = x1 + dt * (num - 1);
    return (x1 + xn) * num / 2;
}
int main() {
    cin >> n >> k;
    if(n < k) {
        while(++i, 1) {
            l = k / (i + 1) + 1;
            r = k / i;
            if(l <= n || l == r) break;
        }
        ans += sigma(k % n, i, n - l + 1);
    }
    while(++i, 1) {
        l = k / (i + 1) + 1;
        r = k / i;
        if(l == r) break;
        ans += sigma(k % r, i, r - l + 1);
    }
    for(register int i = 2; i <= l; ++i) {
        ans += k % i;
    }
    if(n >= k)cout << ans + k * (n - k);
    else cout << ans;
    return 0;
}