Luogu 1445 樱花

BZOJ 2721

唔，太菜了弄不来。

先通分：得到　　$\frac{x + y}{xy} = \frac{1}{n!}$

两边乘一下　　　$(x + y)n! - xy = 0$

两边加上$(n!)^2$，然后因式分解：　　$(x - (n!))(y - (n!)) = (n!)^2$。

本题中要求$x,y$是正整数，如果我们求出了$x - n!$和$y - n!$是正整数，那么$x$和$y$也会是正整数，然后这两个式子只要确定了一个就可以求出另外一个，所以本题的答案就是$(n!)^2$的因数个数，把$n!$先分解质因数然后所有质因数数量乘以$2$$ + 1$乘起来就好了。

暴力分解质因数是$n \sqrt{n}$的，不能承受，我们在线性筛的时候可以直接筛出到所有数的最小质因子，然后直接除掉即可。

时间似乎是每一个数的质因数个数$???$。

Code：

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int N = 1e6 + ;

const ll P = 1e9 + ;

int n, pCnt = , pri[N], lp[N];

ll cnt[N];

bool np[N];

inline void sieve() {

    lp[] = ;

    for(int i = ; i <= n; i++) {

        if(!np[i]) pri[++pCnt] = i, lp[i] = i;

        for(int j = ; j <= pCnt && i * pri[j] <= n; j++) {

            np[i * pri[j]] = ;

            if(i % pri[j] == ) {

                lp[i * pri[j]] = pri[j];

                break;

            }

            lp[i * pri[j]] = pri[j];

        }

    }

/*    for(int i = 1; i <= n; i++)

        printf("%d ", lp[i]);

    printf("\n");    */

}

int main() {

    scanf("%d", &n);

    sieve();

    for(int i = ; i <= n; i++) {

        int tmp = i;

        for(; tmp != ; tmp /= lp[tmp]) ++cnt[lp[tmp]];

    }

    for(int i = ; i <= pCnt; i++) cnt[pri[i]] *= ;

    ll ans = 1LL;

    for(int i = ; i <= n; i++) ans = ans * (1LL + cnt[i]) % P;

    printf("%lld\n", ans);

    return ;

}