51nod 1189 算术基本定理/组合数学

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

用到了算术基本定理的性质求解N!所有素因子的个数，和乘法原理计算所有组合。

 #include<bits/stdc++.h>

 using namespace std;

 #define LL long long

 LL mod=1e9+;

 int num[];

 bool is[];

 void init()

 {

     is[]=is[]=;

     int m=sqrt(+0.5);

     for(int i=;i<=m;++i)

     {

         if(!is[i]){

             for(int j=i*i;j<=;j+=i)

                 is[j]=;

         }

     }

 }

 int f(int N,int K)

 {

     int s=;

     while(N){

         s+=N/K;

         N/=K;

     }

     return s;

 }

 int main()

 {

     int N,M,i,j,k,p=;

     init();

     cin>>N;

     M=N;

     for(i=;i<=M;++i)

     {

         if(!is[i])

             num[p++]=f(M,i);

     }

     LL res=;

     for(i=;i<p;++i)

     {

         res=res*(*num[i]+)%mod;

     }

     res=(res+)*%mod;

     cout<<res<<endl;

     return ;

 }

 /*

 公式化简为 : (X-N!)*(Y-N!)=(N!)2        假设N!=P1a1*P2a2*......*Pnan

 那么ans=π(2*ai+1)| 1<=i<=n ,但是要求X<=Y,所以除以二之后向上取整就好了。

 */