Luogu P2261 [CQOI2007]余数求和

最近中考放假几天都在怼一道BJOI2018的水题,但卡死在90pts跑不动啊!

然后今天发现终于过了然而Hack的数据全RE了然后就开始找新的题目来找回信心。

然后发现智能推荐里有这道题,然后想了1min才想到CQOI到底是哪里的原来是重庆呵

其实还是一道比较好的除法分块入门题。动一下脑子就可以做了。

我们先观察一下最基础的式子:

(sum_{i=1}^n k mod i)

然后我们利用取余的基本性质,即(k mod i=k-ilfloorfrac{k}{i} floor),把原式化为:

(sum_{i=1}^n k-ilfloorfrac{k}{i} floor),然后把k提取出来,即有(nk-sum_{i=1}^n ilfloorfrac{k}{i} floor)

然后我们考虑如何求解(sum_{i=1}^n ilfloorfrac{k}{i} floor),而求它的关键就在于这个(lfloorfrac{k}{i} floor)

我们令(t=lfloorfrac{k}{i} floor),然后我们通过样例(k=5)的情况来观察一下规律:

(i) (1) (2) (3) (4) (5) (6) (7) (8) (9) (10)
(t) (5) (2) (1) (1) (1) (0) (0) (0) (0) (0)

手玩找规律一下可以发现一个显然的性质所有的(t)都是连续的一段

然后我们考虑把所有相同的(t)都一起计算,这样我们可以估计它的复杂度大约为(O(sqrt n))

然后我们令我们当前处理的区间左端为(l),然后我们想一下如何推出(r)然后我们继续手玩发现

  • (t=0)时,(r=n)
  • (t e 0)时,(r=min(n,lfloorfrac{k}{t} floor))

然后这样我们下一次操作只要使(l=r+1)即可

然后对于每一块内,我们计算它们的和:

(sum=frac{tcdot (r-l+1)cdot (l+r)}{2})

然后我们就做下去即可附上超级精简CODE

#include<cstdio>
using namespace std;
long long n,k,t,ans,l,r;
inline int min(int a,int b)
{
    return a<b?a:b;
}
int main()
{
    scanf("%lld%lld",&n,&k); ans=n*k;
    for (l=1;l<=n;l=r+1)
    t=k/l,r=t?min(n,k/t):n,ans-=t*(r-l+1)*(l+r)>>1;
    printf("%lld",ans);
}
原文地址:https://www.cnblogs.com/cjjsb/p/9174894.html