自动搬运

查看原文

来自洛谷，原作者为

	Huami360 菜是原罪

搬运于2025-08-24 21:25:10，当前版本为作者最后更新于2018-08-01 09:36:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

做了题还是忍不住要写一发题解，感觉楼下的不易懂啊。 本题解使用latex纯手写精心打造。

题意：求$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$的正整数解总数。

首先，不会线筛素数的先去做下LuoguP3383。

开始推导。

那么$\frac{1}{x}$和$\frac{1}{y}$肯定是小于$\frac{1}{n!}$的。所以$x$和$y$肯定都是大于$n!$的。

我们令

原式变为

等式两边同乘$x*n!*(n!+k)$得

移项得

∴

∵$x$为正整数

∴$\frac{(n!)^2}{k}+n!$为正整数，$\frac{(n!)^2}{k}$为正整数,因为$k=y-n!$，而$y$是可以取到任意正整数的，所以$k$也可以取到任意正整数，所以这道题就变成了求$(n!)^2$的约数个数。

求约数个数，线筛的时候我们已经预处理出每个数的最小质因子，直接$for$一遍$1-n$，不断除以它的最小公约数，直到变成1为止，同时每次都使记录质因数的指数的数组++，这就完成了对每个数分解质因数，最后把这些质因数的指数+1乘起来就行了。时间复杂度$O(nlogn)$

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define rep(i,m,n) for(int i=m;i<=n;++i)
#define dop(i,m,n) for(int i=m;i>=n;--i)
#define lowbit(x) (x&(-x))
#define INF 2147483647
using namespace std;
inline int read(){
    int s = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0',ch = getchar();
    return s * w;
}
const int MAXN = 1000010;
const int MOD = 1000000007;
int n;
int c[MAXN], v[MAXN], prime[MAXN], cnt;
int ans = 1;
int main(){
    n = read();
    /////////
    rep(i, 2, n){
       if(!v[i]){
         v[i] = i;
         prime[++cnt] = i;
       }
       rep(j, 1, cnt){
          if(prime[j] > v[i] || prime[j] > n / i) break;
          v[i * prime[j]] = prime[j];
       }
    }
    ///////线筛
    rep(i, 1, n){  //求质因数指数
       for(int j = i; j != 1; j /= v[j])
          c[v[j]]++;
    }
    rep(i, 1, n) ans = (long long)ans * (c[i] * 2 + 1) % MOD; //long long保存中间过程，既节省了时间、空间复杂度，又不会溢出
    printf("%d\n", ans);
    return 0;
}