如何找到“数字乘积”的因子数？ [英] How to find Number of Factors of "product of numbers"

问题描述

我正试图找出大数乘积的因数。

I m trying to find number of factors of product of big numbers.

问题陈述是：假设您得到N个数字（假设N = 10 ），每个数字< =1000000。
如何查找此类数字乘积的数量。

The problem statement is this : Suppose you are given N numbers(let say N = 10), each number <= 1000000. How to find the number of factors of the product of such numbers.

请问有人可以提供一种有效的算法

Can someone please provide an efficient algorithm for doing this.

示例：

1）N = 3，数字为3、5、7

1) N = 3 and Numbers are 3, 5, 7

Ans = 8（1、3、5、7、15、21、35、105）

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

2） N = 2，数字为5、5

2) N = 2 and Numbers are 5, 5

Ans = 3（1、5和25）

Ans = 3 (1, 5 and 25)

推荐答案

问题的编辑在这里

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

这篇关于如何找到“数字乘积”的因子数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！