洛谷P2261 余数求和
2024-08-25 23:06:10
整除分块的小应用。
考虑到 k % x = k - (k / x) * x
所以把 x = 1...n 加起来就是 k * n - (k / i) * i
i = 1...k(注意这里是k)
对于这个 k / i 就可以整除分块了。
还要注意 k 与 n 的大小关系。
当 k < n 的时候,只需减去不大于k的部分即可。
当 n < k 的时候,注意别让 i > n 就行了。
#include <cstdio>
#include <algorithm>
typedef long long LL; inline void solve() {
LL n, k;
if(scanf("%lld%lld", &n, &k) == EOF) {
exit();
}
LL ans = n * k;
for(LL i = , j; i <= std::min(k, n); i = j + ) {
j = std::min(k / (k / i), n);
ans -= (k / i) * ((i + j) * (j - i + ) / );
} printf("%lld", ans);
return;
} int main() {
solve();
return ;
}
AC代码
最新文章
- Windows Server 2012 虚拟化实战:SCVMM的安装和部署
- 基于 Asp.Net的 Comet 技术解析
- 运行maven项目
- 一些XMLHttpRequest的例子代码
- MEF(Managed Extensibility Framework )的入门介绍
- yii2 批量插入or更新
- Ubuntu 系统下 mongodb 安装和配置
- IDOC、ALE、EDI三者之间的区别于联系
- PLSQL数据导入
- hadoop初学
- 基于Verilog的串口发送程序
- LeetCode--No.006 ZigZag Conversion
- File处理
- 769. Max Chunks To Make Sorted
- 谱聚类(Spectral clustering)(1):RatioCut
- JAVA并发设计模式学习笔记(二)—— Single Threaded Execution Pattern
- mongo删除、添加分片
- 基于套接字通信的简单练习(FTP)
- Qtp测试中的密码问题
- orancle数据库 插入数量 值大于 1000 解决方案