ural 1049

题目：http://acm.timus.ru/problem.aspx?space=1&num=1049

题意：给十个数，假设十个数相乘后所有因子个数为 sum，求的 N = sum % 10；

忘了是根据什么了，有一个结论：任何一个数都可以写成：M = P1 ^ a1 * P2 ^ a2 * P3 ^ a3 ~~~~~ Pn ^ an;那么 M 的因子个数就是 sum = （a1 + 1) * (a2 + 1) * (a3 + 1) ~~~(an + 1); ai < 10000，注意随时取余

View Code

 1 const int N = 10010;
 2 int prime[15010];
 3 int tnum[N];
 4 bool vis[N];
 5 int num;
 6 int ans;
 7 void is_prime()  // 打印素数表
 8 {
 9     int i,j;
10     for(i = 2; i < N ;i++)
11     {
12         if(!vis[i])
13         {
14             prime[num ++] = i;
15             for(j = 1; j * i < N; j++)
16             {
17                 if(vis[i * j]) continue;
18                 vis[i * j] = true;
19             }
20         }
21     }
22 }
23 void cal(int n)
24 {
25     int i;
26     for(i = 0; i < num; i++)  // 计算每个素因子的个数
27     {
28         if(!n) return ;
29         if(n % prime[i] == 0)
30         {
31             int sum = 0;
32             while(n % prime[i] == 0)
33             {
34                 sum ++;
35                 n /= prime[i];
36             }
37             tnum[prime[i]] += sum;
38         }
39     }
40 }
41 int main()
42 {
43     num = 0;
44     is_prime();
45     int n,i;
46     ans = 1;
47     _clr(tnum,0);
48     //freopen("data.txt","r",stdin);
49     for(i = 0; i < 10; i++)
50     {
51         scanf("%d",&n);
52         if(n == 1) continue;
53         cal(n);
54     }
55     for(i = 0; i < N; i++)
56     {
57         if(tnum[i]) 
58         {
59             ans *= ((tnum[i] + 1) % 10);  // 随时取余
60             ans %= 10;
61         }
62 
63     }
64     printf("%d\n",ans);
65     return 0;
66 }