ural 1049. Brave Balloonists（标准分解式，数论）

1049. Brave Balloonists

Time limit: 2.0 second
Memory limit: 64 MB

Ten mathematicians are flying on a balloon over the Pacific ocean. When they are crossing the equator they decide to celebrate this event and open a bottle of champagne. Unfortunately, the cork makes a hole in the balloon. Hydrogen is leaking out and the balloon is descending now. Soon it will fall into the ocean and all the balloonists will be eaten by hungry sharks.

But not everything is lost yet. One of the balloonists can sacrifice himself jumping out, so that his friends would live a little longer. Only one problem still exists: who is the one to get out. There is a fair way to solve this problem. First, each of them writes an integer ai not less than 1 and not more than 10000. Then they calculate the magic number N that is the number of positive divisors of the product a1*a2*…*a10. For example, the number of positive integer divisors of 6 is 4 (they are 1,2,3,6). The hero (a mathematician who will be thrown out) is determined according to the last digit of N. Your task is to find this digit.

Input

Input contains ten integer numbers (each number is in separate line).

Output

Output a single digit from 0 to 9 — the last digit of N.

Sample

input	output
1 2 6 1 3 1 1 1 1 1	9

题意：

十个数学家乘气球飞行在太平洋上空。当横越赤道时，他们决定庆祝一下这一壮举。于是他们开了一瓶香槟。不幸的是，软木塞在气球上打了一个洞，氢气泄漏，气球开始下降，眼看就要落入海中，所有人将要被鲨鱼吃掉。

但是尚有一线生机--若其中一人牺牲自己跳下去的话，那他的朋友们还能多活一会儿。但仍然有一个问题存在--谁跳下去？所以他们想了一个非常公平的办法来解决这个问题--首先，每人写一个整数ai（1≤ai≤10000）；然后计算出a1×a2×a3×a4×……×a10的积的约数的个数N。例如，6的约数有4个（1、2、3、6），则N为4。这位牺牲自己的英雄将由N的个位数来决定（编号为N的个位数加1的人要跳下去）。你的任务是求出N的个位。

思路：进行的标准分解，根据（标准分解）：任何一个自然数都可以被分解成有限个素数相乘的形式

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 bool ks[10005]= {true};
 7 int kiss[10005]={0};
 8 int ss[10005]= {0};
 9 int number=1;
10 
11 
12 int main()
13 {
14 //    freopen("input.txt","r",stdin);
15     memset(ks,true,sizeof(ks));
16     ks[2]=true;
17     int i=2;
18     ss[0]=2;
19     while(i<=10000)
20     {
21         if(!ks[i])
22         {
23             i++;
24             continue;
25         }
26         ss[number++]=i;
27         for(int j=2; i*j<=10000; j++)
28         {//求出小于10001的所有素数
29             ks[i*j]=false;
30         }
31         i++;
32     }
33     int s=10;
34     while(s)
35     {//录入数据
36         int a;
37         cin>>a;
38         while(1)
39         {//处理录入的a，对a进行标准分解
40             if(ks[a])
41             {
42                 kiss[a]++;
43                 break;
44             }
45             i=0;
46             while(i<number)
47             {
48                 if(a%ss[i]==0)
49                 {
50                     kiss[ss[i]]++;
51                     a=a/ss[i];
52                 }
53                 i++;
54             }
55         }
56         s--;
57     }
58     int sgin=1;
59     for(i=2; i<=10000; i++)
60     {//统计余数的个数
61         sgin*=(kiss[i]+1);
62         sgin%=10;
63         if(sgin==0)
64             break;
65     }
66     cout<<sgin<<endl;
67     return 0;
68 }

View Code