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

传统题

1000ms

512MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

原题来自：HackerRank Equations

【题意】

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

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

一个整数 $n$ 。

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

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

对于 30% 的数据， $n\le 100$ ；对于全部数据， $1\le n\le 10^6$ 。