poj 3604 Professor Ben

质因数分解；牛人推导公式(1^3+2^3+……+(1+a1)^3)*……*(1^3+2^3+……+(1+ai)^3)……

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #include<iomanip>
 5 #include<cmath>
 6 #include<string>
 7 using namespace std;
 8 int prime[3001],m;
 9 bool f[3001];
10 void init()
11 {
12     int i,j;
13     m=0;
14     memset(f,0,sizeof(f));
15     for(i=2;i<3000;i++)
16     {
17         if(f[i]==0)
18         {
19             prime[m++]=i;
20             for(j=i*i;j<3000;j+=i)
21                 f[i]=1;
22         }
23     }
24 }
25 int main()
26 {
27     init();
28     __int64 sum,temp;
29     int i,j,a,n,t;
30     scanf("%d",&t);
31     while(t--)
32     {
33         scanf("%d",&n);
34         sum=1;
35         for(i=0;i<m&&prime[i]*prime[i]<=n;i++)
36         {
37             if(n%prime[i]==0)
38             {
39                 j=0;
40                 while(n%prime[i]==0)
41                 {
42                     n/=prime[i];
43                     j++;
44                 }
45                 temp=(j+1)*(j+2)/2;
46                 sum*=temp*temp;
47             }
48         }
49         if(n>1)
50             sum*=9;
51         printf("%I64d
",sum);
52     }
53     return 0;
54 }

View Code