http://acm.hdu.edu.cn/showproblem.php?pid=4473
比赛的时候，这道题我由于思路始终不能从对n开平方深入到正解的对n开三次方，很遗憾没有出。赛后听了题解，恍然大悟。
以为自己平时思路挺灵活的，现在想想比赛的时候思路还真是僵化啊。
题目意思：
定义f(x) = 满足(a * b)|x的有序对(a,b)的个数。
然后输入一个n，求f(1) + f(2) + ... + f(n)
废话不多说，此题的关键在于：
把原题的条件(a * b)|x 转化为 a * b * y = x
然后就很好计算了，就是，输入一个n，计算有多少有序对(a, b ,y)满足a*b*y<=n
不妨设a<=b<=y
则，a<=n^(1/3) , b<=sqrt(n/a)
那么
对于三个数字都相同的情况，只计算一次: i i i
对于三个数字中有两个相同的情况，计算3次: i i j, i j i, j i i
对于均不相同的情况，计算6次: a b y ,a y b ,b a y ,b y a, y a b ,y b a
程序如下：注意在HDOJ上使用%I64d，但是现场赛使用%lld
1 #include<cmath>
2 #include<cstdio>
3 using namespace std;
4 typedef long long ll;
5 ll pow2(ll n){//高精度开平方
6 ll m=pow(n,0.5);
7 while(m*m<=n) m++;
8 while(m*m>n) m--;
9 return m;
10 }
11 ll pow3(ll n){//高精度开立方
12 ll m=pow(n,1.0/3);
13 while(m*m*m<=n) m++;
14 while(m*m*m>n) m--;
15 return m;
16 }
17 int main()
18 {
19 int C=0;
20 ll n;
21 while (~scanf("%I64d",&n)){
22 ll m=pow3(n),ans=m;//第一种情况m个
23 for(int i=1;i<=m;i++){
24 ll ni=n/i,k=pow2(ni);//n/i下面多次用到，只计算一次，常数优化
25 ans+=(ni/i + k - i*2)*3;//计算第二种情况，其中i i j有(ni/i - i)个，i j j有(k - i)个
26 for(int j=i+1;j<=k;j++)
27 ans+=(ni/j - j)*6;//计算第三种情况
28 }
29 printf("Case %d: %I64d\n",++C,ans);
30 }
31 return 0;
32 }