bzoj1968[Ahoi2005] COMMON 约数研究

本文主要是介绍bzoj1968[Ahoi2005] COMMON 约数研究，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：bzoj1968
题目大意：
求1到n各个数约数个数的和。$1≤n≤10^6$

题解：
…我怎么这么蠢。
一直在想怎么化这个公式：

$$\sum_{i=1}^{n}\sum_{d|n}1$$
？？？我真搞笑
直接for一遍 $n$就好了。
对于一个数$i$，1到 $n$中就会有$n/i$个数是它的倍数，即有 $n/i$个数有 $i$这个约数。
所以就直接$O(n)$累加。。
好像有 $O(\sqrt{n})$的算法。不过没看。= =

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;int main()
{//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);LL n,i,ans=0;scanf("%lld",&n);for(int i=1;i<=n;i++) ans+=n/i;printf("%lld\n",ans);return 0;
}

这篇关于bzoj1968[Ahoi2005] COMMON 约数研究的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---