题意描述

求方程:

$\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;
}

【Violet】樱花-题解