BZOJ 1257 余数之和题解

2024-10-07 05:51:53

这道题是一道整除分块的模板题；

首先，知道分块的人应该知道，n/i最多有2*sqrt(n)种数,但这和余数有什么关系呢?

注意，只要n/i的值和n/(i+d)的值一样，那么n%i到n%(i+d)的值就是一个等差数列！因为n/i=n/(i+1)*(i+1)=n/i*(i+1)=n/i*i+n/i;

所以在向下取整的情况下它是公差为n/i的等差数列；

因此运用分块的性质和等差数列求和公式就可以切掉这道题；

#include <bits/stdc++.h>

using namespace std;

long long n,k;

int main()

{

    cin>>n>>k;

    long long ans=n*k;

    for(register long long l=,r;l<=n;l=r+){

        if(k/l==) r=n;

        else r=min(k/(k/l),n);

        ans-=((r-l+)*(k/l*l)+(r-l+)*(r-l)/*(k/l));

    }

    cout<<ans;

}

最新文章

热门文章