1189 阶乘分数

基准时间限制：1 秒空间限制：131072 KB

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
思路：通分可得xy-（x+y）N！=0；然后（x-N！）*（y-N！）=xy-(x+y)N!+N!^2;

即可得到（x-N!）(y-N!) = N!^2;那么左边的就是右边的因数，那么求下右边这个数的因数有几个就可以了，分解质因数即可，然后乘法原理；

 1 #include <stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #include<math.h>
 5 #include<algorithm>
 6 #include<iostream>
 7 using namespace std;
 8 bool prime[1000006];
 9 typedef long long LL;
10 int ans[1000006];
11 LL cnt[100006];
12 const LL mod = 1e9+7;
13 LL quick(LL n,LL m,LL mod);
14 int main(void)
15 {
16         int i,j;
17         for(i = 2; i <= 1000; i++)
18         {
19                 if(!prime[i])
20                         for(j = i; (i*j) <= 1000000; j++)
21                                 prime[i*j] = true;
22         }
23         int cn = 0;
24         for(i = 2; i <= 1000000; i++)
25                 if(!prime[i])ans[cn++] = i;
26         LL n;
27         LL ni = quick(2,mod-2,mod);
28         scanf("%lld",&n);
29         for(i = 0; i < cn; i++)
30         {
31                 LL k = n;
32                 while(k)
33                 {
34                         cnt[i] += k/ans[i];
35                         k/=ans[i];
36                 }
37         }
38         LL sum = 1;
39         for(i = 0; i <= cn; i++)
40         {
41                 sum = sum*(2*cnt[i]+1)%mod;
42         }
43         sum+=1;
44         sum = sum*ni%mod;
45         printf("%lld
",sum);
46         return 0;
47 }
48 LL quick(LL n,LL m,LL mod)
49 {
50         LL ask = 1;
51         n %= mod;
52         while(m)
53         {
54                 if(m&1)
55                         ask = ask*n%mod;
56                 n = n*n%mod;
57                 m>>=1;
58         }
59         return ask;
60 }