题目来自:http://acm.timus.ru/problem.aspx?space=1&num=1049
题目的大意是：
输入10个整数：a1,a2,...., a10.
假设他们的乘积：k = a1*a2*....*a10.
求k的公约数的个数N的个位数上是什么数字。
解这个题目的关键在于，怎样求出一个数的公约数的个数.(如6的公约数的个数为4(1,2,3,6)).
很多人一看，很简单啊，直接循环1~k，总可以求出来。
这话虽没错，但只会使蛮力，不懂取巧，除了让自己的形象看起来更像一头牛，通常也会遇到效率上的瓶颈。
这里输入的10个数，有可能会很大，因此直接暴力搜索约数的个数是不行的，第4个测试数据会被卡下来。
事实上这类的题目用上一点点数论的知识，就可以得出很巧的答案。
通常，在对一个整数进行分解的时候，我们常常把这个数写成素数的形式，这里我们也试试这样来分析一下。
假设:
k = (p1^a1)*(p2^a2)*.....*(pi^ai) (p1,...,pi是素数, ai > 0)
显然，k的所有约数，肯定都是这些素数们的乘积，比如：
6 = 2*3
因此，6的约数为:2,3,2*3.
刚好是： (1+1)*(1+1) - 1 = 3.
问题其实就等价于：在a1个P1,a2个p2，....，ai个Pi,共(a1+a2+...+ai)个数中，通过相乘，可以找出多少个互不相等的数。
这其实就排列组合的问题了。
对于i个集合，每个集合各有aj个相同的元素( 1 =< j <= i),现在要从各个集合中抽出一定数量的元素，组成另一个集合，有多少种取法？
每个集合有aj个元素，我们可以共有(aj+1)种取法（分别取0,1,...,aj个元素出来）
因此对i个结合，共有(a1+1)*(a2+1)*....*(ai+1) - 1种取法（减1是排除掉各个集合里都只抽出0个元素的情况）
现在回到我们的题目中来。
对于， k = (p1^a1)*(p2^a2)*.....*(pi^ai)。k的约数的个数为：(a1+1)*(a2+2)*....*(ai+1) - 1
但上面并没有包括1进去（1必然是k的约数）
因此最后的结果是：(a1+1)*(a2+2)*....*(ai+1) - 1 + 1.
由此可见，我们只要对各个输入数求一下他们的素数的表示形式，就很容易可以计算出他们的约数的个数了。
而素数相对来说，是相当稀疏的，因此效率上必然比暴力搜索要好很多。
#include<iostream> #include<math.h> #include<map> using namespace std; #define MAXV (10002) //整数的最大上限。 static map<int,int> si; //用保存素数的个数，如si[3] = 5,表示3^5 //下面两个数组用于筛法求素数表。 static bool isPrime[MAXV]; static int prime[MAXV]; //求素数。 static void MakePrime() { memset(isPrime,1,sizeof(isPrime)); memset(prime,0,sizeof(prime)); for(int i=2; i < MAXV; ++i) { if(isPrime[i]) { prime[++prime[0]] = i; for(int j = 2;j * i < MAXV;++j) { isPrime[i*j] = false; } } } } //获取整数num的素数表示形式 //如 6 = 2*3 12 = (2^2)*(3) void GetDivisor(int num) { for(int i = 1;i <= prime[0] && prime[i] <= num;++i) { int t = prime[i]; int s = t; while(num % s == 0) { si[t]++; s *= t; } } } int main()// { int i = 0; int k ; MakePrime(); si.clear(); while(i++ < 10) { cin >> k; GetDivisor(k); } __int64 num = 1; map<int,int>::iterator iter = si.begin(); for(;iter != si.end();++iter) num *=1+ iter->second; cout << num%10; return 0; }