如何找到"数字乘积"的因子数

Question

我试图找到大数量产品的因素.

问题陈述是这样的:假设给你N个数字(假设N = 10),每个数字<= 1000000.如何找到这些数字乘积的因子数.

有人可以提供一个有效的算法来做到这一点.

示例:

1)N = 3,数字为3,5,7

Ans = 8(1,3,5,7,15,21,35,105)

2)N = 2且数字为5,5

Ans = 3(1,5和25)

Answer 1

因式分解每个数字成的素因子和它们的重数列表,L(n) = { p_i , k_i }用于若干Ñ = Π p _我^{ķ _我}.对于这样的n的除数的数是ND(L(n))= Π(k _i +1)所有系数的乘积,每个系数递增1(这包括1和n本身作为n的除数).这对应于挑选每个人中的一个,一个,...... k _i乘以.

为了计算任意数量的乘积的ND,对每个数进行分解并合并它们的分解,其中在匹配素数的情况下,它们的系数被加在一起.然后计算合并分解的ND.

要将多个因子分解在一起,首先要合并其中两个; 然后合并结果和下一个结果; 然后合并最后的结果和下一个分解,依此类推.这称为折叠.或者更好地将它们成对合并,然后以相同的成对方式合并结果,依此类推,只剩下一个合并结果.这与自下而上的mergesort的完成方式类似.

Answer 2

编辑问题就在这里

http://discuss.codechef.com/questions/15943/numfact-editorial

int total = 0, N = 0, Number;
scanf ("%d", &total);
while (total--)
{
    scanf ("%d", &N);
    map<int, int> Counter;
    for (int i = 0; i < N; i++)
    {
        scanf ("%d", &Number);
        for (int j = 2; j * j <= Number; j++)
        {
            while (Number % j == 0)
            {
                Counter[j]++;
                Number /= j;
            }
        }
        if (Number > 1) Counter[Number]++;
    }
    int Answer = 1;
    for (map<int, int>::iterator it = Counter.begin(); it != Counter.end(); it++)
        Answer *= (it->second + 1);
    printf ("%d\n", Answer);
}

这已经被接受了.

样本输入和输出:

7
3
3 5 7
3
2 4 6
2
5 5
10
2 2 2 2 2 2 2 2 2 2 
1
100
10
10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
10
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 

8
10
3
11
9
1681
3721