余数之和
思想:
首先看到数据范围为1e9级别,故可以想到用分块思想,优化到$O(2\sqrt{n})$
$k \% i$ <==> $k - [\frac{k}{i}]*i$
则$k \% \sum_1^n$ $<==>$ $n*k\ -\ \sum_{i=1}^n[\frac{k}{i}]*i$
代码:
#include <iostream>
using namespace std;
typedef long long LL;
LL sum_primes(int n, int k) {
//k % i = k - [k / i] * i ---> k % [1, n] = n*k - k / [1,n]*i
LL res = (LL)n * k;
for(int i = 1; i <= n; ) {
if(k < i) break; //此时往后全为0,不用操作了
int x = k / i, y = min(k / x, n); //区间有极限值为n,防止越界
//求区间总值 * x --- > 等差数列求和:n * (a1 + an) / 2
res -= x * (LL)(y - i + 1) * (i + y) / 2;
i = y + 1; //操作下一个区间
}
return res;
}
int main() {
int n, k;
cin >> n >> k;
cout << sum_primes(n, k) << endl;
return 0;
}