本文介绍了如何找到“数字乘积”的因子数?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我正试图找出大数乘积的因数。
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更多推荐
如何找到“数字乘积”的因子数?
发布评论