时间限制	内存限制
`1000 ms`	`65536 KB`

# 题目描述

给定 $n$ 个数 $a_1, \cdots, a_n$ ，求 $m = a_1 \times a_2 \times \cdots \times a_n$ 的正因数个数。

# 输入

第一行一个正整数 $t$ 代表数据组数， $1 \le t \le 100$ 。

对于每组数据，第一行一个正整数 $n$ ，代表数字个数， $1 \le n \le 10$ 。第二行 $n$ 个正整数 $a_i$ ， $1 \le a_i \le 10^9$ 。

# 输出

对于每组数据，输出一行一个正整数，代表 $m$ 的不同正因数的个数，其中 $m = a_1 \times a_2 \times \cdots \times a_n$ 。

# 输入样例

	4
	2
	6 2
	1
	17
	1
	1000000000
	3
	11 45 14

# 输出样例

	6
	2
	100
	48

# 样例解释

对于第一组样例， $6 \times 2 = 12$ ， $12$ 的正因数有 $1, 2, 3, 4, 6, 12$ 共 $6$ 个。

对于第二组样例， $17$ 的因数有 $1,17$ 共 $2$ 个。

# 题解：线性筛 + 数论

考虑一个数的质因数分解：

$m = p_1^{c_1} p_2^{c_2} \cdots p_k{c_k}$

其中 $p_1, \cdots, p_k$ 均为质数。我们知道，此时 $m$ 的正因数个数为 $(c_1 + 1) (c_2 + 1) \cdots (c_k + 1)$ 。

我们考虑将 $a_1, \cdots, a_n$ 都进行质因数分解，再将同质数的质数相加，就得到了 $m$ 的质因数分解。但是我们注意到，最大的质数还是 $10^9$ 这个量级的，有什么办法吗？

不难发现，大于 $\sqrt {10^9}$ 的质因数在每次分解 $a_i$ 时至多只会出现一次，因此我们考虑将 $\sqrt {10^9}$ 之前的质数用线性筛先筛出来，然后用它们对 $a_i$ 进行分解，如果最后 $a_i$ 不为 $1$ ，则剩下的必定是一个大于 $\sqrt {10^9}$ 的质数，我们把它记下来即可。具体细节参考代码实现。

时间复杂度为 $O(tn \sqrt {值域})$ 。

参考代码：

	#include <stdio.h>
	#include <stdbool.h>
	#include <string.h>

	typedef long long ll;

	int primeCnt, bigPrimeCnt, prime[50010], bigPrime[15], bigPrimePower[15], primePower[50010];
	bool notPrime[100010];

	void GetPrime()
	{
	notPrime[1] = true;

	for (int i = 2; i <= 100000; ++ i)
	{
	if (!notPrime[i])
	prime[ ++ primeCnt] = i;

	for (int j = 1; j <= primeCnt && 1ll * i * prime[j] <= 100000; ++ j)
	{
	notPrime[i * prime[j]] = true;

	if (i % prime[j] == 0)
	break;
	}
	}

	return;
	}

	int main()
	{
	// freopen("H.in", "r", stdin);
	// freopen("H.out", "w", stdout);

	GetPrime();
	int T;
	scanf("%d", &T);

	while (T -- )
	{
	bigPrimeCnt = 0;
	memset(bigPrime, 0, sizeof(bigPrime));
	memset(bigPrimePower, 0, sizeof(bigPrimePower));
	memset(primePower, 0, sizeof(primePower));
	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; ++ i)
	{
	int a;
	scanf("%d", &a);

	for (int j = 1; j <= primeCnt; ++ j)
	while (a % prime[j] == 0)
	{
	a /= prime[j];
	++ primePower[j];
	}

	if (a > 1)
	{
	int ind = 1;

	while (ind <= bigPrimeCnt && bigPrime[ind] != a)
	++ ind;

	if (ind > bigPrimeCnt)
	bigPrimeCnt = ind;

	bigPrime[ind] = a;
	++ bigPrimePower[ind];
	}
	}

	ll ans = 1;

	for (int i = 1; i <= primeCnt; ++ i)
	ans *= (primePower[i] + 1);

	for (int i = 1; i <= bigPrimeCnt; ++ i)
	ans *= (bigPrimePower[i] + 1);

	printf("%lld\n", ans);
	}

	return 0;
	}

质数线性筛