洛谷 P2261 [CQOI2007]余数求和

新学的知识点:除法分块。
题解:https://www.luogu.org/blog/Capella/solution-p2261

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
#define ll long long
using namespace std;
ll n,k,ans;
int main(){
    cin>>n>>k;
    for(ll l=1,t,r;l<=n;l=r+1){
        t=k/l;
        if(t==0)r=n;
        else r=min(k/t,n);
        ans-=t*(l+r)*(r-l+1)/2;
    }
    cout<<ans+n*k;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注