余数之和

时间限制: 1 Sec  内存限制: 128 MB

题目描述

给出正整数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<=10^9

 

输出

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

 

样例输入

复制样例数据

5 3

样例输出

7
/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

LL n, k;

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%lld %lld", &n, &k);
	LL ans = 0;
	if(n > k) ans += (n - k) * k, n = k;
	for (LL i = 1; i <= n; i++){
		LL t = k / i; //整除的值
		LL l = i, r = k / t; //整除值的左右区间，就是k/i == t(l <= i <= r);
		if(r > n) r = n;
		ans += (k - t * l + k - r * t) * (r - l + 1) / 2;//等差数列求和
		i = r;//下个区间从r+1开始
	}
	printf("%lld\n", ans);

	return 0;
}
/**/