hdu4473 & cf293C

http://codeforces.com/contest/293/problem/C

 1 /*
 2 http://codeforces.com/contest/293/problem/C
 3 题意：(a+b+c)^3=a^3+b^3+c^3+n,给你n的值，求多少组a,b,c是正整数的解；
 4 　　化解3(a+b)(a+c)(b+c)=n，a,b,c等价
 5 　　不妨设a<=b<=c，再设a+b=x,a+c=y,b+c=z ,则x<=y<=z;
 6 　　则
 7 　　x^3<=n/3,
 8 　　x*y^2<=n/3, 
 9 　　x*y*z=n/3;
10 */
11 #include<cstdio>
12 #include<cstring>
13 #include<cstdlib>
14 #include<iostream>
15 #include<cmath>
16 #include<algorithm>
17 using namespace std;
18 typedef long long LL;
19 typedef long double LD;
20 LL n;
21 
22 int main(){
23     while (cin>>n){
24         if (n%3){
25             cout<<0<<endl;
26             continue;
27         }
28         n/=3;
29         int up=(int)(pow((LD)n,1.0/3)+0.5);
30         int ret=0;
31         for (int i=1;i<=up;i++){
32             if (n%i) continue;
33             int limt=int(sqrt((LD)n/i)+0.5);
34 
35             for (int j=limt;j>=i;j--){
36                 if ((n/i)%j) continue;
37                 int k=n/i/j;
38                 if(i+j<=k) break;
39                 if ((i+k-j)%2 ) continue;
40                // cout<<i<<" "<<j<<" "<<k<<endl;
41                 int b=(i+k-j)/2,a=i-b,c=k-b;
42                 if (a<=0 || c<=0) continue;
43                 if (a==b){
44                     if (b==c) ret+=1;
45                     else ret+=3;
46                 }else {
47                     if (b==c) ret+=3;
48                     else if (a==c)ret+=3;
49                     else ret+=6;
50                 }
51             }
52         }
53         cout<<ret<<endl;
54     }
55 
56     return 0;
57 }

View Code

hdu4473

转自：http://www.cnblogs.com/hundundm/archive/2012/11/17/2775191.html

题目意思：

　　定义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

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<cstdlib>
 7 using namespace std;
 8 typedef long long LL;
 9 typedef  double LD;
10 LL n;
11 LL pow2(LL n){
12     LL m=pow(n,1.0/2);
13     while (m*m<=n) m++;
14     while (m*m>n) m--;
15     return m;
16 }
17 LL pow3(LL n){
18     LL m=pow(n,1.0/3);
19     while (m*m*m<=n) m++;
20     while (m*m*m>n) m--;
21     return m;
22 }
23 int main(){
24     int cas=0;
25     while (~scanf("%I64d",&n)){
26 
27         LL up=pow3(n);
28         LL ret=0;
29         for (int i=1;i<=up;i++){
30             LL ni=n/i,limt=pow2(ni);
31             for (int j=i;j<=limt;j++){
32                LL c=ni/j;
33                if (i==j) ret+=(c-j)*3+1;
34                else ret+=(c-j)*6+3;
35             }
36         }
37         printf("Case %d: %I64d\n",++cas,ret);
38 
39     }
40     return 0;
41 }

View Code