Luogu P2261 [CQOI2007]余数求和

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

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

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

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

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

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

然后我们利用取余的基本性质，即\(k\ mod\ i=k-i\lfloor\frac{k}{i}\rfloor\)，把原式化为：

\(\sum_{i=1}^n k-i\lfloor\frac{k}{i}\rfloor\)，然后把k提取出来，即有\(nk-\sum_{i=1}^n i\lfloor\frac{k}{i}\rfloor\)

然后我们考虑如何求解\(\sum_{i=1}^n i\lfloor\frac{k}{i}\rfloor\)，而求它的关键就在于这个\(\lfloor\frac{k}{i}\rfloor\)

我们令\(t=\lfloor\frac{k}{i}\rfloor\)，然后我们通过样例\(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\ne 0\)时，\(r=min(n,\lfloor\frac{k}{t}\rfloor)\)

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

然后对于每一块内，我们计算它们的和：

\(sum=\frac{t\cdot (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);

}

巴特西

Luogu P2261 [CQOI2007]余数求和

最新文章

热门文章