【题目链接】

点击打开链接

【算法】

要求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 ; }

最新文章

  1. 解决EditText和ScrollView滑动冲突问题
  2. yaf框架使用(centos6.5)
  3. 使用 IntraWeb (42) - 测试读取 SqLite (一)
  4. Html-Css-div标签设定-剧中
  5. ElasticSearch 概念解析
  6. angularjs学习总结一(表达式、指令、模型)
  7. Android MediaStore与Media.EXTERNAL_CONTENT_URI
  8. jQuery判断滚动条是上滚还是下滚,且是否到达底部或顶部
  9. 《C++ Primer》读书笔记—第一章 开始
  10. 【XSY3154】入门多项式 高斯消元
  11. 用tar压缩xz格式出错
  12. java字符串根据正则表达式让单词首字母大写
  13. VSC软件快捷键
  14. Java入门系列
  15. 【CF809E】Surprise me!(动态规划,虚树,莫比乌斯反演)
  16. 20170921 DEV功能页面
  17. sqlserver 数据迁移
  18. 利用gotty在web浏览器模拟终端登录
  19. css 基础1
  20. springboot中使用自定义的properties属性

热门文章

  1. 图的最小生成树——Kruskal算法
  2. 【HTML/XML 4】实例分析HTML和XML的不同
  3. F题
  4. Java设计模式之(工厂模式)
  5. Gearman 初窥【转载】
  6. poj2689素数问题
  7. IdHttp 资料
  8. [Android] 随时拍图像处理部分总结及源码分享
  9. poj -1185 炮兵阵地 (经典状压dp)
  10. PAT (Advanced Level) 1035. Password (20)