算法笔试-编程练习-好题-03

这是一道非常综合的质数类的题目，值得仔细理解。

题目描述

n个正整数ai，希望你求出这些数的阶乘全部乘在一起生成的大数有多少个因子

输入描述

第一行输入一个正整数n。

第二行输入n个正整数ai​，用空格隔开

1≤n≤2×

1≤ai≤

输出描述

一个整数，代表这个乘积的因子数量，由于答案可能过大，请对+7取模.

样例

输入

3
1 2 3

输出

6

说明

1!*2!*3!=12,共有1,2,3,4,6,12六个因子。

题目分析

【题目类型：寻找素数、因数分解、动态规划】

这是质因数分解类题目比较综合的一道，我们首先来理解题意：求1!*2!*3!=12有多少个因数。每个合数都可以被描述为若干质数次方的乘积，例如：12 = ，那么如何求因子数量呢？

对于2我们有3种取法，取0个，1个和2个，对于3我们有2种取法，0个和1个，因此12共有3*2个因子，也就是指数+1的累乘，也就是(2+1)*(1+1)。

有了这样的公式我们的思路就清晰了：找到最终大数的每个质因数的指数。

因为大数是通过阶乘求得的，那么必定很多数字会被乘很多次，所以直觉上我们需要先统计每个数字使用的次数，阶乘描述的是1-n的连城，也就是1-n之间所有数字的使用次数+1。对于这种对于指定区间同时+上一个数字的操作，我们可以使用【差分数组】，用O(1)的时复杂度实现。最后用O(n)的时间复杂度复原（详见代码）。

有了每个数字的使用频次，接下来我们就希望找到每个数字的质因数及其指数。逐一分解时间复杂度过高，我们可以首先计算出指定区间内全部的指数（详见代码）。

再通过遍历质数的方式统计每个数字对该质数的指数，这里可以使用动态规划进行加速，我们假设数字i是指数p的倍数，那么 power[i] = power[i//p] +1（详见代码）。

我们遍历所有数字，累加（数字使用的频次*其质因数的指数），得到的结果就可以带回最初的公式中了。

【注意】除了上述算法外，python还有一个小细节需要注意，就是 ans = ans*(cnt+1) % mod这句话，不要写成ans *= (cnt+1) % mod，这样的写法会导致ans事实上没有被取模，从而导致涉及到大数乘法，计算速度变慢。

代码：

mod = 10**9 +7

n = int(input())
arr = list(map(int, input().split()))
max_num = max(arr)

# 用【查分数组--每次更新O(1)时间复杂度】统计每个数字被乘的次数
pre = [0]*(max_num+2)
for a in arr:
    pre[1] += 1
    pre[a+1] -= 1
for i in range(1, max_num+1):
    pre[i] += pre[i-1]

# 【埃式筛选素数】
primes = [2]
is_prime = [True] * (max_num+1)
p = 3
while p <= max_num:
    if is_prime[p]:
        primes.append(p)
        for i in range(p*p, max_num+1, p):
            is_prime[i] = False
    p += 2

# 统计每个素因数次方（对于整体阶乘积）,同时计算因数的数量
ans = 1
for p in primes:
    cnt = 0
    power = [0]*(max_num+1)
    for i in range(p, max_num+1, p):
        power[i] = power[i//p] + 1
        cnt += pre[i]*power[i]
    if cnt != 0:
        ans = ans*(cnt+1) % mod
print(ans % mod)