题意描述

求方程:

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

的正整数解的组数。

为防止输出过大，请输出答案对$10^9 + 7$取模的结果。

（ps.原题还是很有意思的，感兴趣的读者可以点击这里）

输入格式

仅有一行，包含一个正整数$n$。

输出格式

输出一个正整数，表示最终答案对$10^9 + 7$取模的值。

Input & Output ‘s examples

Input ‘s eg

Output ‘s eg

102426508

样例解释

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

数据范围和约定

对于$30\%$的数据，保证$0 \leq n \leq 100$。

对于$100\%$的数据，保证$0 \leq n \leq 10^7$。

分析

又是一道比较麻烦的数论……

将原式通分，得 $\frac{x + y}{xy} = \frac{1}{n!}$

交叉相乘，就成了： $xy - n!(x + y) = 0$

在两边加上$(n!)^2$，就成了 $(n!)^2 + xy - n!(x + y) = (n!)^2$

之后对左边因式分解，可得 $(x - n!)(y - n!) = (n!)^2$

我们设$a = (x - n!)$，$b = (y - n!)$，则$ab = (n!)^2$

根据唯一分解定理，可知 $n! = \prod_{i = 1}^k p_i^{c_i}$

则 $ab = (n!)^2 = \prod_{i = 1}^k p_i^{2c^i}$

$n!$是一个确定的数，因此我们只需要确定$a , b$ ，就确定了$x , y$。

又因为$b = \frac{(n!)^2}{a}$，则我们确定了$a$，同时也就确定了$b$。

因此我们只需要统计$a$的数目即可。

又因为$a$是$(n!)^2$的因式，因此$a$的数目为 $\prod_{i = 1}^k 2c_i + 1$

先用欧拉筛筛一遍，之后利用唯一分解定理算出所有$c_i$，最后乘起来即可。

时间复杂度$O(n \log n)$，足以通过本题。

剩下的见代码注释。

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define ll long long
#define pb push_back
#define MP make_pair
#define ull unsigned long long
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(a))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

using namespace std;

const int N = 10001;
const int M = 1000001;
const int HA = 1e9 + 7;

int prime[M] , flag[M] , num = 0;
int cnt[M];
ll ans = 1;

void IS_Prime(int n){   //这是一个魔改之后的欧拉筛，其中flag[i]表示i的最小质因子。
    rep(i , 2 , n){
        if(!flag[i])flag[i] = i , prime[++ num] = i;
        rep(j , 1 , num){
            if(prime[j] > flag[i] || prime[j] > n / i) break;
            flag[i * prime[j]] = prime[j];
        }
    }
}

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    int n; scanf("%d" , &n);
    IS_Prime(n);
    rep(i , 1 , n){     //利用最小质因子进行唯一分解
        for(int j = i; j != 1; j /= flag[j]){
            cnt[flag[j]] ++;
        }
    }
    rep(i , 1 , n) ans *= (cnt[i] * 2 + 1) , ans %= HA;
    printf("%lld\n" , ans);

    return 0;
}