BZOJ-1257 [CQOI2007]余数之和

链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1257

$Time\;Limit:\;5\;Sec$

$Memory\;Limit:\;128\;MB$

Description

给出正整数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$

Input

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

$1\le n ,k \le10^9$

Output

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

Sample Input

$5\;3$

Sample Output

$7$

题解

找出每一段$(int)\frac{x}{i}$相等的区间使用等差数列求和即可

//Time: 20ms Memory:1288kB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, k, res, i = 1;
int main()
{
	scanf("%lld%lld", &n, &k);
	while(i <= n)
	{
		ll d = k / i, r = d ? min(k / d, n) : n;
		res += (i + r) * (r - i + 1) / 2 * d;
		i = r + 1;
	}
	printf("%lld", n * k - res);
	return 0;
}