洛谷——P2261 [CQOI2007]余数求和
2024-09-30 22:19:13
P2261 [CQOI2007]余数求和
关键在于化简公式,题目所求$\sum_{i=1}^{n}k\mod i$
简化式子,也就是$\sum_{i=1}^{n}(k-\frac{k}{i}\times k)$
$=n*k-\sum_{i=1}^{n}\frac{k}{i}\times k$
$⌊ \frac{m}{k}⌋$ 共有 $O( √ m)$ 种取值,直接计算。总时间复杂度 $O( √ m)$
观察下图:
你会发现$\frac{k}{i}$是有规律的,或者说相同的紧挨着,分布在同一个块中
确定$\frac{k}{i}$取值相同的区间$[l,r]$,$r=min(n,k/(k/l))$
$k/l$代表这一部分的取值,$k/(k/l)$就是区间的右端点
确定了区间,那么根据等差数列求和公式$\frac{(S1+Sn)\times n}{2}$
#include<bits/stdc++.h> #define LL long long
using namespace std; LL n,k; int main()
{
scanf("%lld%lld",&n,&k);
LL ans=n*k;
for(LL l=,r;l<=n;l=r+){
if(k/l!=) r=min(k/(k/l),n);
else r=n;
ans-=(k/l)*(r-l+)*(l+r)/;
} printf("%lld\n",ans); return ;
}
最新文章
- Centos7.2 Systemd 方式编译 Mysql5.7.11
- js库中$冲突的解决方法
- Xcode 6以上版本如何创建一个空的工程(Empty Application)
- Cloudra公司CCP:DS——认证数据专家
- java加载配置文件
- (转)Python获取当时时间
- 基于Tkinter利用python实现颜色空间转换程序
- Chapter 2 Open Book——35
- 开机后发现Win7桌面上什么都没有该如何恢复
- 201521123096《Java程序设计》第十二周学习总结
- Python开发 文件操作
- (Python3) 运行结果 = 10,40 的困扰我一顿饭时间的 代码
- ssh 报error: kex protocol error: type 30 seq 1
- LCA(ST倍增)
- Filter防止用户访问一些未被授权的资源
- kafka的log存储解析——topic的分区partition分段segment以及索引等(转发)
- vue2.0 之事件处理器
- setTimeout设置不起作用
- Ehcache配置参数简介
- JavaWeb基础—JSP