Sol
整除分块入门题
现在让你求得是
\sum_{i = 1}^{n} k \ mod \ i
模运算这种东西就是带余除法,然后你发现余数你也很不好算。就考虑把模运算改成带余除法的形式
我们知道: x \div i = \lfloor \frac{x}{i} \rfloor + x - (i \times \lfloor \frac{x}{i} \rfloor)
所以现在要求的东西就是
\sum_{i=1}^{n} x - (i \times \lfloor \frac{x}{i} \rfloor)
n \times x - \sum_{i=1}^{n} i \times \lfloor \frac{x}{i} \rfloor
n 的范围是10^9,所以后面那一块东西就用整除分块做掉
比如说你打表发现 n=10 的时候,得到的\lfloor \frac{x}{i} \rfloor分别是 10 5 3 2 2 1 1 1 1 1
所以\lfloor \frac{x}{i} \rfloor是有规律的,并且结论是:假如一个块的起始位置是l,那么终止位置r= \lfloor \frac{x}{\lfloor \frac{x}{i} \rfloor} \rfloor
现在前面还乘了一个 i ,观察到 \sum_{i=1}^{n} i 这是一个等差数列。所以可以直接等差数列求一段的和
事实上,只要是积性函数,都会满足这个性质
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int SIZE = 1e5 + 5;
int n, k;
namespace ae86 {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
return *s++;
}
inline int read() {
int a = 0, b = 1, c = fetch();
while (!isdigit(c))b ^= c == '-', c = fetch();
while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
return b ? a : -a;
}
}
using ae86::read;
signed main()
{
n = read(), k = read();
int ans = n * k;
for (int l = 1, r; l <= n; l = r + 1) {
if (k / l != 0) r = std::min(k / (k / l), n);
else r = n;
ans -= (k / l) * (r - l + 1) * (l + r) / 2;
// printf("l:%d r:%d ans:%d\n", l, r, ans);
}
printf("%lld\n", ans);
return 0;
}
Comments | NOTHING