政务网站队伍建设情况,怎么做网页游戏代理,华大基因 建设网站,搜索引擎营销的概念水题 发布时间: 2017年6月25日 14:06 最后更新: 2017年7月3日 09:27 时间限制: 1000ms 内存限制: 128M 描述 平均因数个数的统计对于估算数论题目复杂度具有非常重要的意义。小A同学听了今天的课后#xff0c;于是想要自己写一个程序#xff0c;求出1到n的平均因数个数… 水题 发布时间: 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]
84221111
我们可以发现光1就出现了4次2出现了2次剩下的都出现了1次。这也就意味着我们可以进行统计
我们统计除数为d的出现次数那么d出现的次数可以表示为k [n/d]-[n/(d1)]
那么它对答案的贡献就是d*k下一次d就变成了d1
当我们第一次发现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 d1;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;
}
