水題

發(fā)布時(shí)間: 2017年6月25日 14:06?? 最后更新: 2017年7月3日 09:27?? 時(shí)間限制: 1000ms?? 內(nèi)存限制: 128M

描述

平均因數(shù)個(gè)數(shù)的統(tǒng)計(jì)對(duì)于估算數(shù)論題目復(fù)雜度具有非常重要的意義。小A同學(xué)聽了今天的課后，于是想要自己寫一個(gè)程序，求出1到n的平均因數(shù)個(gè)數(shù)。小A當(dāng)然會(huì)啦！但是他想考考你。

輸入

多組輸入數(shù)據(jù)（不超過1000組）。
每組一個(gè)正整數(shù)n(n≤109)，如題目所述。

輸出

輸出1到n中的平均因數(shù)個(gè)數(shù)，精確到9位小數(shù)。

樣例輸入1 4 20170703 樣例輸出1 2.000000000 16.974173533 平均因數(shù)的個(gè)數(shù)計(jì)數(shù)，很簡(jiǎn)單嘛

1~n的因數(shù)的個(gè)數(shù)總數(shù)為

而由公式我們可以將上面的式子變換成為

也就是

對(duì)這個(gè)東西進(jìn)行求和也是比較簡(jiǎn)單的，注意不能暴力求和，因?yàn)闀r(shí)間復(fù)雜度太高了

我們考慮一個(gè)例子，當(dāng)n為8的時(shí)候

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

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

我們可以發(fā)現(xiàn)光1就出現(xiàn)了4次，2出現(xiàn)了2次，剩下的都出現(xiàn)了1次。這也就意味著，我們可以進(jìn)行統(tǒng)計(jì)

我們統(tǒng)計(jì)除數(shù)為d的出現(xiàn)次數(shù)，那么d出現(xiàn)的次數(shù)可以表示為k = [n/d]-[n/(d+1)]

那么，它對(duì)答案的貢獻(xiàn)就是d*k，下一次d就變成了d+1

當(dāng)我們第一次發(fā)現(xiàn)d出現(xiàn)1次的時(shí)候，這代表著下面所有的d也都只會(huì)出現(xiàn)一次了，我們求出這時(shí)候的分母f

將f循環(huán)到1，并直接暴力算出結(jié)果。

代碼：

#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; }

總結(jié)

以上是生活随笔為你收集整理的2017西安交大ACM小学期数论 [水题]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。