[2007CQOI]余数求和-整除分块

题目大意

输入给出两个正整数$n$和$k$,
计算的值,

其中$k\mod i$表示k除以i的余数。例如
$G(10,5)=5\mod1+5\mod2+5\mod3+5\mod4
+5\mod5 \\ +……+5\mod10=0+1+2+1+0+5+5+5+5+5=29$
$(n,k \leqslant 10^9)$

分析

首先对$G(n,k)$化简

得到上式,如果暴力枚举$1\leqslant i\leqslant n$,因为$n\leqslant 10^9$,绝对会超时。。。
但是观察$\left \lfloor \frac{k}{i} \right \rfloor$这个式子,发现对于一个区域内的$i$得数不变
于是就有了整除分块
令$l,r=min(\frac{k}{\left \lfloor \frac{k}{l} \right \rfloor},n)$分别为$\left \lfloor \frac{k}{i} \right \rfloor$相等的区间左端点与右端点,累加$\left \lfloor \frac{k}{l} \right \rfloor\times \frac{(l+r) \times (r-l+1)}{2}$(高斯求和),每次使$l=r+1$,循环到$r=min(n,k)$即可

注意!!!本题中$k$可能小于$n$,加个特判即可

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#define ri register int
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mid ((l+r)>>1)
typedef long long LL;
template <typename T>
inline T read (T &x){char ch=getchar();x=0;while(ch>'9'||ch<'0')ch=getchar();while(ch<='9'&&ch>='0')x *= 10,x += ch - '0',ch = getchar();return x;}//读入优化,可无视
LL n,k,ans;
int main()
{
read(n);read(k);ans=n*k;
for(LL l=1,r;l<=n;l=r+1) {
if(k/l!=0) r=k/(k/l)<n?k/(k/l):n;
else r=n;//重要的特判,否则会除以0错误
ans-=(k/l)*(r-l+1)*(l+r)/2;
}
printf("%lld",ans);
return 0;
}