nod1189 阶乘能拆的和

题目链接 1/N! = 1/X + 1/Y，给出N，求满足条件的整数解的个数Mod 10^9 + 7

化成x=(n!)^2/k+n!，问题转化为求(n!)^2的约数个数和。由于结果要求模10^9+7。所以得出的结果是(ans+1)/2%mod，进一步地变成(ans+1)*q%mod. 其中q是2模mod的乘法逆元。类似于之前那个求n^2因数和的题 因为是阶乘 所以用了阶乘的那个递归 之前小伙伴用了一个超级麻烦的扩展欧几里得求逆元，自己根据课件优化了一下==

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=1e6+7;
const long long mod=1e9+7;
LL sta[maxn],pnum[maxn],top;
LL cal(LL n,LL v){
    if(n==0)return 0;
    return (n/v+cal(n/v,v)%mod)%mod;
}
bool notprime[maxn];
LL prime[maxn/10],top1;
void getprime(){
    for(LL i=2;i<=maxn;i++){
         if(!notprime[i]){
             prime[top1++]=i;
             notprime[i]=1;
         }
         for(LL j=0;j<top1&&i*prime[j]<=maxn;j++){
             notprime[i*prime[j]]=1;
             if(i%prime[j]==0)break;
         }
    }
}
void fenjie(LL m){
    top=0;
    memset(sta,0,sizeof(sta));
    memset(pnum,0,sizeof(pnum));
    for(LL i=0;i<top1&&prime[i]<=m;i++){
        sta[top]=prime[i];
        pnum[top++]=cal(m,prime[i]);//某素因子存在的个数
    }
}
void extend_Euclid(LL a,LL b,LL &x,LL &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return ;
    }
    extend_Euclid(b,a % b,x,y);
    LL tmp = x;
    x = y;
    y = tmp - (a / b) * y;
}
int main()
{
    //freopen("cin.txt","r",stdin);
    LL n,x,y;
    extend_Euclid(2LL,mod,x,y);//2的逆元 用来乘到分子上
   // cout<<x<<endl;
    LL ni=x;
    ni=(ni+mod)%mod;
    getprime();
    while(~scanf("%lld",&n)){
    fenjie(n);
    LL ans=1;
    for(LL i=0;i<top;i++){
        LL temp=(2*pnum[i]%mod+1)%mod;
        ans=(ans*temp)%mod;
    }
    printf("%lld\n",(ans+1)*ni%mod);
    }
    return 0;
}