[原创]51nod 1189 阶乘分数 [因子个数+逆元]【数论】

[原创]51nod 1189 阶乘分数 [因子个数+逆元]【数论】

2017-01-11 23:28:45 Tabris_ 阅读数：293

---

博客爬取于2020-06-14 22:42:16
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54354875

---

题目连接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1189
----------------------------------------------------------------------------------.
1189 阶乘分数
题目来源： Spoj
基准时间限制：1 秒 空间限制：131072 KB 分值: 80 难度：5级算法题 收藏 关注
1/N! = 1/X + 1/Y（0< x<=y），给出N，求满足条件的整数解的数量。例如：N = 2，1/2 = 1/3 + 1/6，1/2 = 1/4 + 1/4。由于数量可能很大，输出Mod 10^9 + 7。
Input
输入一个数N（1 <= N <= 1000000)。
Output
输出解的数量Mod 10^9 + 7。
Input示例
2
Output示例
2
-------------------------------------------------------------------------------------.

解题思路:
对于这种题目就是转换下式子
由于
$\frac{1}{N!}=\frac{1}{X}+\frac{1}{Y}$
$\frac{1}{X}=\frac{1}{N!}-\frac{1}{Y}$
$\frac{1}{X}=\frac{N!-Y}{Y*N!}$
$Y*N!=(N!-X)*Y$
同理可得
$X*N!=(N!-Y)*X$

可得
$X*N!*Y*N!=(N!-X)*Y*(N!-Y)*X$
化简为
$N!*N!=(N!-X)*(N!-Y)$

这个时候由于N事确定的，那么将$(N!-X)$看成一个整体,那么其为$(N!)^2$的因子,$(N!-X)$有多少个X就有多少个,
Y同理.

这样的话就是求$(N!)^2$的因子个数$\prod_{i=0}^{prime-num}(1+a_i)$了.

但是由于题目要求,$X<=Y$,所以结果是$[\frac{\prod_{i=0}^{prime-num}(1+a_i)}{2}]_{向上取整}$

除2很简单,求一下逆元即可

附本题代码

# include <bits/stdc++.h>
using namespace std;
# define abs(x) ((x>=0)?(x):-(x))
typedef long long int LL;
const int MOD = 1e9+7;
const int N = 1e6+7;
/*******************************************/
int prime[N],kp;
int Is_or[N][2];
void Prime(){
    kp = 0;
    memset(Is_or,true,sizeof(Is_or));
    Is_or[0][0]=Is_or[1][0]=0;
    for(int i=2;i<=1000000;i++){
        if(Is_or[i][0]) Is_or[i][1]=kp,prime[kp++]=i;
        for(int j=0;j<kp&&prime[j]*i<=1000000;j++){
            Is_or[prime[j]*i][0]=0;
            if(0==i%prime[j]) break;
        }
    }
    return ;
}
LL a[80000];
LL qmod(LL a,LL b){
    LL res= 1ll;
    while(b){
        if(b&1)res=res*a%MOD;
        b>>=1;
        a=a*a%MOD;
    }
    return res;
}
int main(){
    //printf("%I64d\n",qmod(2,MOD-2));
    Prime();
    //printf("%d\n",kp);
    //for(int i=0;i<kp;i++)printf("%d\n",prime[i]);
    int n;
    scanf("%d",&n);
    int tem ;
    for(int i=1;i<=n;i++){
        tem = i;
        for(int j=0;j<kp&&tem>=prime[j];j++){
            if(Is_or[tem][0]) {a[Is_or[tem][1]]++;break;}
            while(0==tem%prime[j]) a[j]++,tem/=prime[j];
        }
    }
    LL ans = 1ll;
    for(int i=0;i<kp;i++){
        ans*=((a[i]<<1)+1);
        ans%=MOD;
    }
    printf("%I64d\n",(ans+1)*500000004%MOD);
    return 0;
}