首页 > 其他 > 详细

整除分块

时间:2021-01-09 23:30:23      阅读:37      评论:0      收藏:0      [点我收藏+]

整除分块

what is it?

我们来专心看一下下面这个式子
\(\sum\limits_{i=1}^n \lfloor \frac n i \rfloor\)
\(in general\),我们会花\(O(n)\)的时间解决
\(however\),我们会发现\(\lfloor \frac {11} 6 \rfloor==\lfloor \frac {11} 7 \rfloor==\lfloor \frac {11} 8 \rfloor\)
换言之,从\(\lfloor \frac n 1 \rfloor\)\(\lfloor \frac n n \rfloor\),最多只会有\(\sqrt n\)个数(证明有点复杂,可以自行BFS)
我们可以试着去枚举这\(\sqrt n\)个数
然后会发现,同一个数个结尾是\(\lfloor \frac n {\lfloor \frac n i \rfloor} \rfloor\)
那么可以用下面这个代码解决……

int fenk(int n){
	int tot=0;
	for(int i=1,j;i<=n;i=j+1){
		j=n/(n/i);
		tot=tot+(n/i)*(j-i+1);
	}
	return tot;
}

because of the lack of the time
\(That\) \(all\)

整除分块

原文:https://www.cnblogs.com/yang-RA-NOI/p/14256463.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!