如何找到“数字乘积”的因子数？

本文介绍了如何找到“数字乘积”的因子数？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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)

推荐答案

问题的编辑在这里

discuss.codechef/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