检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。
题面
题目描述
给出正整数 和 ,请计算:
其中 表示 除以 的余数。
输入格式
输入只有一行两个整数,分别表示 和 。
输出格式
输出一行一个整数表示答案。
输入输出样例
样例输入 #1
10 5
样例输出 #1
29
样例解释 #1
。
数据范围与约定
- 对于 的数据,保证 ;
- 对于 的数据,保证 ;
- 对于 的数据,保证 。
思路
然后使用整除分块计算。设 ,若 ,则 ,否则 。将 减去 (区间内 的平均值 × × 区间长度)。
当 时可知余下部分全为 ,退出循环即可。
代码
#include <iostream>
using std::cin;
using std::cout;
const char endl = '\n';
long long n, k, ans;
int main() {
std::ios::sync_with_stdio(false);
cin >> n >> k;
ans = n * k;
for (long long l = 1, r; k / l && l <= n; l = r + 1) {
r = std::min(k / (k / l), n);
ans -= (r + l) * (k / l) * (r - l + 1) / 2;
}
cout << ans << endl;
return 0;
}