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示例

Output示例

2

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

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define LL long long
 4 LL mod=1e9+7;
 5 int num[1000005];
 6 bool is[1000005];
 7 void init()
 8 {
 9     is[0]=is[1]=1;
10     int m=sqrt(1000000+0.5);
11     for(int i=2;i<=m;++i)
12     {
13         if(!is[i]){
14             for(int j=i*i;j<=1000000;j+=i)
15                 is[j]=1;
16         }
17     }
18 }
19 int f(int N,int K)
20 {
21     int s=0;
22     while(N){
23         s+=N/K;
24         N/=K;
25     }
26     return s;
27 }
28 int main()
29 {
30     int N,M,i,j,k,p=0;
31     init();
32     cin>>N;
33     M=N;
34     for(i=2;i<=M;++i)
35     {
36         if(!is[i])
37             num[p++]=f(M,i);
38     }
39     LL res=1;
40     for(i=0;i<p;++i)
41     {
42         res=res*(2*num[i]+1)%mod;
43     }
44     res=(res+1)*500000004%mod;
45     cout<<res<<endl;
46     return 0;
47 }
48 
49 /*
50 
51 公式化简为 : (X-N!)*(Y-N!)=(N!)2        假设N!=P1a1*P2a2*......*Pnan                     
52 那么ans=π(2*ai+1)| 1<=i<=n ,但是要求X<=Y,所以除以二之后向上取整就好了。
53 
54 */