这是一道非常综合的质数类的题目,值得仔细理解。
题目描述
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 +7n = 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] += 1pre[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] = Falsep += 2# 统计每个素因数次方(对于整体阶乘积),同时计算因数的数量
ans = 1
for p in primes:cnt = 0power = [0]*(max_num+1)for i in range(p, max_num+1, p):power[i] = power[i//p] + 1cnt += pre[i]*power[i]if cnt != 0:ans = ans*(cnt+1) % mod
print(ans % mod)