【AHOI 2005】 约数研究
2024-09-06 06:17:19
【题目链接】
【算法】
要求M,显然可以通过约数个数定理从1..N暴力计算答案,然而n最大10^6,这个算法的时间复杂度是
O(N * sqrt(N))的,不能通过此题
因此我们换一种思路
不妨考虑每个数对答案的“贡献”,若这个数为i,那么1..n中,共有n / i个数是i的倍数,那么i对答案的“贡献”
就是n / i,因此答案应该是 sigma(n / i) (1 <= i <= n)
【代码】
#include<bits/stdc++.h>
using namespace std; long long i,n,ans = ; template <typename T> inline void read(T &x) {
long long f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
} template <typename T> inline void write(T x) {
if (x < ) { putchar('-'); x = -x; }
if (x > ) write(x/);
putchar(x%+'');
} template <typename T> inline void writeln(T x) {
write(x);
puts("");
} int main() { read(n);
for (i = ; i <= n; i++) ans += n / i;
writeln(ans); return ; }
最新文章
- 解决EditText和ScrollView滑动冲突问题
- yaf框架使用(centos6.5)
- 使用 IntraWeb (42) - 测试读取 SqLite (一)
- Html-Css-div标签设定-剧中
- ElasticSearch 概念解析
- angularjs学习总结一(表达式、指令、模型)
- Android MediaStore与Media.EXTERNAL_CONTENT_URI
- jQuery判断滚动条是上滚还是下滚,且是否到达底部或顶部
- 《C++ Primer》读书笔记—第一章 开始
- 【XSY3154】入门多项式 高斯消元
- 用tar压缩xz格式出错
- java字符串根据正则表达式让单词首字母大写
- VSC软件快捷键
- Java入门系列
- 【CF809E】Surprise me!(动态规划,虚树,莫比乌斯反演)
- 20170921 DEV功能页面
- sqlserver 数据迁移
- 利用gotty在web浏览器模拟终端登录
- css 基础1
- springboot中使用自定义的properties属性