這題的結(jié)果[f(1)+f(2)+...+f(n)]其實(shí)就等價(jià)于x*y*z<=n的解的個(gè)數(shù)，然后的方法幾乎就是暴力枚舉了?，F(xiàn)場(chǎng)比賽的時(shí)候沒想到這一點(diǎn)，太杯具了，浪費(fèi)了兩個(gè)小時(shí)的思考時(shí)間。其實(shí)我們的做法應(yīng)該是可行的，因?yàn)閒(n)具有積性性質(zhì)，也就是若gcd(n, m)=1，則f(n*m)=f(n)*f(m)。而當(dāng)p為質(zhì)數(shù)時(shí)，f(p^k)=(k+1)*(k+2)/2，這樣就能把f(n)數(shù)列的前n項(xiàng)和化成一堆多項(xiàng)式的加和。然后用合并同類項(xiàng)的思想，用容斥原理搞，可是代碼量太大了，沒打出來(lái)。。。

今天賽題被掛到HDOJ上以后用上面說(shuō)的枚舉方法打了一下，交上去居然WA，調(diào)了半天也沒發(fā)現(xiàn)錯(cuò)誤，最后才懷疑是sqrt和pow函數(shù)的精度問題，馬上查了一下解題報(bào)告，果然都是手動(dòng)寫的開平方和開立方函數(shù)。加上以后就過(guò)了~~

/** hdu4473/win.cpp* Created on: 2012-11-17* Author : ben*/ #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <queue> #include <set> #include <map> #include <stack> #include <string> #include <vector> #include <deque> #include <list> #include <functional> #include <numeric> #include <cctype> using namespace std; typedef long long LL;inline LL sqrt2(LL n) {LL m = (LL)sqrt(n + 0.0);while(m * m <= n)m++;while(m * m > n)m--;return m; }inline LL sqrt3(LL n) {LL m = (LL) pow(n, 1 / 3.0);while (m * m * m <= n)m++;while (m * m * m > n)m--;return m; }LL work(LL n) {LL ret = 0;LL t1 = sqrt3(n);ret += t1;for(LL a = 1; a <= t1; a++) {ret += 3 * (n / (a * a) - a);ret += 3 * (sqrt2(n / a) - a);LL t2 = sqrt2(n / a);for(LL b = a + 1; b <= t2; b++) {ret += 6 * (n / (a * b) - b);}}return ret; }int main() { #ifndef ONLINE_JUDGEfreopen("data.in", "r", stdin); #endifint t = 1;LL n;while(scanf("%I64d", &n) == 1) {printf("Case %d: %I64d\n", t++, work(n));}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/moonbay/archive/2012/11/12/2766607.html

總結(jié)

以上是生活随笔為你收集整理的hdu4473的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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