#P2344. *【线性筛】1/x +1/y =1/n! 的方案数

*【线性筛】1/x +1/y =1/n! 的方案数

原题来自:HackerRank Equations

【题意】

求以下不定方程的正整数解 (x,y)(x,y) 的数目。

1x+1y=1n!\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}

【输入格式】

一个整数 nn

【输出格式】

一个整数,表示有多少对 (x,y)(x,y) 满足题意。答案对 109+710^9+7 取模。

2
3

【样例解析】

共有三个数对 (x,y)(x,y) 满足条件,分别是 (3,6)(3,6),(4,4)(4,4)(6,3)(6,3)

【数据范围与提示】

对于 30% 的数据,n100n\le 100; 对于全部数据,1n1061\le n\le 10^6