1. 问题描述：
给定一个整数 n，求有多少正整数数对 (x,y) 满足 1/x+1/y=1/n!。
输入格式
一个整数 n。
输出格式
一个整数，表示满足条件的数对数量。答案对 10 ^ 9 + 7 取模。
数据范围
1 ≤ n ≤ 10 ^ 6
输入样例：
2
输出样例：
3
样例解释
共有三个数对 (x,y) 满足条件，分别是 (3,6),(4,4),(6,3)。
来源：https://www.acwing.com/problem/content/description/1296/
2. 思路分析：
对于这种给出数学式子的题目一般都是先要化简一下数学公式，也即需要推导一下看一下有什么性质
因为n!是一个正整数，所以看后面的那个式子即可，相当于问的是有多少正整数x使得n!n!能够整除x - n!，并且满足下面的关系，若x < n!那么y是负数与题目中x，y都是正整数就矛盾了，所以x >= n!，也即x - n! >= 0，所以相当于问的是有多少个数字是n!n!的约数，与之前197题阶乘分解的题目是类似的：
最终得到的n!n!约数个数为，直接使用197题的思路求解即可，在分解n的阶乘的时候计算质因子出现的次数：
3. 代码如下：
from typing import List
class Solution:
count = 0
# 线性筛求解2~n之间的质数(包括数字n)
def init(self, n: int, primes: List[int], st: List[int]):
for i in range(2, n):
if st[i] == 0:
primes[self.count] = i
self.count += 1
j = 0
while primes[j] * i < n:
st[primes[j] * i] = 1
if i % primes[j] == 0: break
j += 1
def process(self):
n = int(input())
primes = [0] * (n + 10)
st = [0] * (n + 10)
self.count = 0
res, mod = 1, 10 ** 9 + 7
self.init(n + 1, primes, st)
for i in range(self.count):
# s为当前质数出现的次数
p, j, s = primes[i], n, 0
while j > 0:
s += j // p
j //= p
res = res * (2 * s + 1) % mod
return res
if __name__ == '__main__':
print(Solution().process())
