[BZOJ1257/Luogu2261][CQOI2007]余数求和(数论分块)

发布于 2018-01-17  71 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1257/Luogu2261][CQOI2007]余数求和(数论分块)

Description

给出正整数n和k,计算G(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值,其中k mod i表示k除以i的余数。例如G(10, 5)=5 mod 1 + 5 mod 2 + 5 mod 3 + 5 mod 4 + 5 mod 5 …… + 5 mod 10=0+1+2+1+0+5+5+5+5+5=29

Http

BZOJ
Luogu

Tag

数论分块

题目大意

求\(\sum_{i=1}^{n} K\ mod\ i \)

解决思路

由于\(a%b=a-b*\lfloor \frac{a}{b} \rfloor\),所以式子可以化为
\[\sum_{i=1}^{n} (K-i*\lfloor \frac{K}{i} \rfloor ) \\ =n*K-\sum_{i=1} \lfloor \frac{K}{i} \rfloor\]
后面这个式子可以数论分块做。
需要注意\(n < K\)的情况,此时分块会浮点溢出(除\(0\)错误),所以要控制循环上界

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long

int main()
{
    ll n,K;scanf("%lld%lld",&n,&K);
    ll ans=0;
    ans=n*K;
    for (ll i=1,last;i<=n;i=last+1)
    {
        if ((ll)(K/i)==0) break;//及时退出,防止除0
        last=min(K/((ll)(K/i)),n);
        ll s1=(last+i)*(last-i+1)/2;
        //cout<<s1<<" "<<ans<<endl;
        ans=ans-s1*(ll)((K/i));
    }
    printf("%lld\n",ans);
    return 0;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1257/Luogu2261][CQOI2007]余数求和(数论分块)


HNCJ OIer 一枚