Loading...

洛谷 P2261[CQOI2007]余数求和

check评论:0 条 remove_red_eye浏览量:337 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-03-16

题目要求的答案是$\sum\limits_{i=1}^n k\%i$

也就是$\sum\limits_{i=1}^n k-i\times\lfloor\frac{k}{i}\rfloor$

整除分块就好了owo

#include <bits/stdc++.h>
using namespace std;
#define int long long 
signed main()
{
    int n,k;
    cin>>n>>k;
    int ans=n*k;
    for(int i=1;i<=n;)
    {
        int l=(k/i);
        if(l==0)
        {
            l=n;
        }
        else
        {
            l=min(n,k/l);
        }
        ans-=((l+i)*(l-i+1)/2)*(k/i);
        i=l+1;
    }
    cout<<ans;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名