[Violet]樱花

题目链接

洛谷
狗粮版

前置技能

1. 初中基础的因式分解
2. 线性筛
3. (O(nlog))的分解质因数
4. 唯一分解定理

题解

首先来分解一下式子

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

通分可化为:

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

两边同时乘(xy*(n!))

[(x+y)n!=xy ]

移项得:

[xy-(x+y)n!=0 ]

两边同时加上((n!)^2)

[xy-(x+y)n!+(n!)^2=(n!)^2 ]

通过十字相乘可因式分解为:

[(x-n!)(y-n!)=(n!)^2 ]

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

[∴x,y>n! ]

又因为(x,y)为正整数,所以((x-n!),(y-n!))也为正整数,所以我们不妨令

[X=(x-n!),Y=(y-n!) ]

则原式可以化为:

[XY=(n!)^2 ]

根据唯一分解定理可知

[n!=P_1^{a_1}P_2^{a_2}P_3^{a_3}...P_n^{a_n}(p_i为质数) ]

((n!)^2)的因数个数为:

[(2*a_1+1)*(2*a_2+1)*(2*a_3+1)*...*(2*a_n+1) ]

所以我们只要算出(a_1,a_2,a_3...a_n)就好了
至于怎么算,线性筛一遍,在分解质因数,求(a_i)就好了

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000000;
const int mod = 1e9+7;
int prime[N+1],a[N+1],js,v[N+1],c[N+1];
int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9')  f=(c=='-')?-1:1,c=getchar();
    while(c>='0'&&c<='9')  x=x*10+c-'0',c=getchar();
    return x*f;
}
void pd(){
    for(int i=2;i<=N;i++){
        if(!prime[i]) a[++js]=i,v[i]=i;
        for(int j=1;j<=js;j++){
            if(i*a[j]>N)  break;
            prime[i*a[j]]=1;
            v[i*a[j]]=a[j];
        }
    }
}
main(){
    int n=read(),x,ans=1;
    pd();
    v[1]=1;
    for(int i=1;i<=n;i++)
        for(int j=i;j!=1;j/=v[j])
            c[v[j]]++;
    for(int i=1;i<=N;i++)
        ans*=(c[i]*2+1),ans%=mod;
    printf("%lld",ans%mod);
}