首页 > 其他 > 详细

洛谷P2261 [CQOI2007]余数求和

时间:2020-04-04 12:50:19      阅读:51      评论:0      收藏:0      [点我收藏+]

\(\large{题目链接}\)
\(\\\)
\(\Large\textbf{Solution: } \large{看到这个数据范围线性也跑不过去,所以推测是推式子简化或者能整体求值。\\原式可化为ans=\sum\limits ^{n}_{i=1}k-\lfloor\dfrac {k}{i}\rfloor\times i = n \times k - \sum \limits ^ {n} _ {i = 1} \lfloor\dfrac{k}{i}\rfloor \times i。\\后面用到了新姿势,除法分块。\\思想就是对于\lfloor\dfrac{k}{i}\rfloor值相同的i,合并一起算,由于\lfloor\dfrac{k}{i}\rfloor的取值大约\sqrt{k}种,所以时间复杂度为\text{O}\left( \sqrt {k}\right)。\\下面说一下具体实现,两个变量l和r,表示\left[l,r\right]的\lfloor\dfrac{k}{i}\rfloor,i \in \left[l,r\right]值相等。\\l初始值为1,r = \Bigg\lfloor\dfrac{k}{\lfloor\dfrac{k}{l}\rfloor}\Bigg\rfloor,l = r + 1。\\感性理解一下为什么这样是对的。}\)
\(\\\)
\(\Large\textbf{Code: }\)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
	ios::sync_with_stdio(false);
	ll n, k;
	cin >> n >> k;
	ll l = 1, r, ans = n * k;
	for (; l <= n; l = r + 1) {
		if (k / l) r = min(k / (k / l), n);
		else r = n;
		ans -= (k / l) * (r - l + 1) * (l + r) / 2;
	}
	cout << ans << endl;
	return 0;
}

洛谷P2261 [CQOI2007]余数求和

原文:https://www.cnblogs.com/Miraclys/p/12631230.html

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