P2261【[CQOI2007]余数求和】

蒟蒻终于不看题解写出了一个很水的蓝题，然而题解不能交了

虽然还看了一下自己之前的博客

题目要求：

做些变化

按\(k<n\)分析，直接从1枚举到k肯定不行，但可以发现\(\lfloor \dfrac{k}{i} \rfloor\)的值只有\(O(\sqrt{k})\)种

• 对于前\(\sqrt{k}\)个数，结果肯定最多有\(\sqrt{k}\)种
• 对于剩下的数，\(num>\sqrt{k} \Rightarrow \lfloor \dfrac{k}{num}\rfloor<\sqrt{k}\)，所以也最多只有\(\sqrt{k}\)种

所以可以按值来算，这个东西好像叫除法分块

如果当前\(\lfloor \dfrac{k}{i}\rfloor\)的值为\(num\)，则下一个可以产生新的值的\(i'=\lfloor \dfrac{k}{num}\rfloor\)+1

然后直接把这\(num\)提出来，用\(num\)乘上\(i\)到\(i'-1\)的和就行是这一段\(\lfloor \dfrac{k}{i}\rfloor \times i\)的结果了乘法分配律

然后注意一下是否\(i'-1>n\)，我就因为这个WA了一次。。

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<iomanip>

#include<cstring>

#define reg register

#define EN std::puts("")

#define LL long long

inline int read(){

	int x=0,y=1;

	char c=std::getchar();

	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}

	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}

	return y?x:-x;

}

LL n,k;

int main(){

	n=read();k=read();

	reg LL ans=0,nex,num;

	LL haha=n*k;

	n=std::min(n,k);

	for(reg int i=1;i<=n;i++){

		num=k/i;

		nex=k/num;//nex就是上文的i'-1

		if(nex>n) nex=n;

		ans+=num*((i+nex)*(nex-i+1)/2);

		i=nex;

	}

	std::printf("%lld",haha-ans);

	return 0;

}