洛谷P2261 [CQOI2007]余数求和 题解
题目链接：P2261 [CQOI2007]余数求和
题意：
给定 n , k n,k n,k ，求
G ( n , k ) = ∑ i = 1 n k ? m o d ? i G(n,k)= \sum_{i=1}^{n}k \bmod i G(n,k)=i=1∑n?kmodi
考虑数论分块
注意到
∑
i
=
1
n
k
?
m
o
d
?
i
=
∑
i
=
1
n
(
k
?
i
?
k
i
?
)
=
n
k
?
∑
i
=
1
n
i
?
k
i
?
\begin{aligned} \sum_{i=1}^{n}k \bmod i &= \sum_{i=1}^{n}\left(k-i\left\lfloor\dfrac{k}{i}\right\rfloor\right)\\ &=nk-\sum_{i=1}^{n}i\left\lfloor\dfrac{k}{i}\right\rfloor \end{aligned}
i=1∑n?kmodi?=i=1∑n?(k?i?ik??)=nk?i=1∑n?i?ik???
若
k
<
n
k < n
k<n ，显然
?
i
>
k
\forall i > k
?i>k 有
?
k
i
?
=
0
\left\lfloor\dfrac{k}{i}\right\rfloor=0
?ik??=0
故可直接计算
n
k
?
∑
i
=
1
k
i
?
k
i
?
nk-\sum_{i=1}^{k}i\left\lfloor\dfrac{k}{i}\right\rfloor
nk?i=1∑k?i?ik??
若
k
≥
n
k \ge n
k≥n ，则判断一下右边界不要超过
n
n
n 即可
代码如下
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> k;int res=n*k;
for(int l=1,r; l<=min(k,n); l=r+1)
{
r=min(k/(k/l),n);
res-=(k/l)*(r-l+1)*(l+r)/2;
}
cout << res << endl;
return 0;
}
转载请说明出处
