【洛谷 P1445】 [Violet]樱花（唯一分解定理）

做了题还是忍不住要写一发题解，感觉楼下的不易懂啊。

本题解使用latex纯手写精心打造。

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

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

开始推导。

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

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

我们令

\[y=n!+k(k∈N^*)
\]

原式变为

\[\frac{1}{x}+\frac{1}{n!+k}=\frac{1}{n!}
\]

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

\[n!(n!+k)+xn!=x(n!+k)
\]

移项得

\[n!(n!+k)=x(n!+k)-xn!=xk
\]

∴

\[x=\frac{n!(n!+k)}{k}=\frac{(n!)^2}{k}+n!
\]

∵\(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;

}

巴特西

【洛谷 P1445】 [Violet]樱花（唯一分解定理）

最新文章

热门文章