洛谷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-ileftlfloordfrac{k}{i}rightrfloorright)\ &=nk-sum_{i=1}^{n}ileftlfloordfrac{k}{i}rightrfloor end{aligned} i=1∑n​kmodi​=i=1∑n​(k−i⌊ik​⌋)=nk−i=1∑n​i⌊ik​⌋​
若 k < n k < n k k forall i > k ∀i>k 有 ⌊ k i ⌋ = 0 leftlfloordfrac{k}{i}rightrfloor=0 ⌊ik​⌋=0

故可直接计算
n k − ∑ i = 1 k i ⌊ k i ⌋ nk-sum_{i=1}^{k}ileftlfloordfrac{k}{i}rightrfloor nk−i=1∑k​i⌊ik​⌋
若 k ≥ n k ge n k≥n ，则判断一下右边界不要超过 n n n 即可

代码如下

#include 
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;
}

转载请说明出处