2017西安交大ACM小学期数论 [水题]

水题

发布时间: 2017年6月25日 14:06   最后更新: 2017年7月3日 09:27   时间限制: 1000ms   内存限制: 128M

描述

平均因数个数的统计对于估算数论题目复杂度具有非常重要的意义。小A同学听了今天的课后，于是想要自己写一个程序，求出1到n的平均因数个数。小A当然会啦！但是他想考考你。

输入

多组输入数据（不超过1000组）。
每组一个正整数n(n≤109)，如题目所述。

输出

输出1到n中的平均因数个数，精确到9位小数。

样例输入1 4 20170703 样例输出1 2.000000000 16.974173533 平均因数的个数计数，很简单嘛

1~n的因数的个数总数为

而由公式我们可以将上面的式子变换成为

也就是

对这个东西进行求和也是比较简单的，注意不能暴力求和，因为时间复杂度太高了

我们考虑一个例子，当n为8的时候

[8/1]+[8/2]+[8/3]+[8/4]+[8/5]+[8/6]+[8/7]+[8/8]

=8+4+2+2+1+1+1+1

我们可以发现光1就出现了4次，2出现了2次，剩下的都出现了1次。这也就意味着，我们可以进行统计

我们统计除数为d的出现次数，那么d出现的次数可以表示为k = [n/d]-[n/(d+1)]

那么，它对答案的贡献就是d*k，下一次d就变成了d+1

当我们第一次发现d出现1次的时候，这代表着下面所有的d也都只会出现一次了，我们求出这时候的分母f

将f循环到1，并直接暴力算出结果。

代码：

#include <cstdio> #include <map> #include <iostream> using namespace std; typedef long long LL; int main(){LL n;while(scanf("%lld",&n) != -1){LL res = 0;LL d = 1;while(d <= n){//++cnt;LL nex = d+1;LL k = n/d - n/nex; if(k == 1){for(int i = n/d;i >= 1;i--){res += n / i;}break;}res += d*k;d = nex;}printf("%.9lf\n",double(res)/n);}return 0; }

总结

以上是生活随笔为你收集整理的2017西安交大ACM小学期数论 [水题]的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。