AcWing 1294. 樱花

一.题目链接

二.思路

首先，遇到这种题目先对公式进行一个推导。
$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$
通分之后得到：$\frac{x+y}{xy}=\frac{1}{n!}$
移项得到：$x\ast n!=(x-n!)y$
固定y之后，问题转化为有多少个x的正整数的取值，使得y为正整数。
然后得到：$y=\frac{x\ast n!}{x-n!}=\frac{(x-n!+n!)n!}{x-n!}=n!+\frac{n{!}^2}{x-n!}$
因为n!是正整数，所以要使$\frac{n{!}^2}{x-n!}$为正整数，至此，问题转化为求解$n{!}^2$的约数个数。

三.代码

#include 
#include 
#include 

using namespace std;

const int N = 1000010, mod = 1e9 + 7;
typedef long long ll;
int primes[N], cnt;
bool st[N];

void init(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; primes[j] * i <= n; j ++)
        {
            st[i * primes[j]] = true;
            if(i % primes[j] == 0) break;
        }
    }
}
int main()
{
    int n;
    cin >> n;
    //预处理质数
    init(n);
    int res = 1;
    //阶乘分解
    for(int i = 0; i < cnt; i ++)
    {
        int p = primes[i];
        int s = 0;
        for(int j = n; j; j /= p) s += j / p;
        res = ((ll)res % mod * (2 * s + 1) % mod) ;
    }
    cout << res << endl;
    return 0;
}

 	

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

四.总结

• 遇到一开始就是公式的式子，需要多转换一下。
• 知识点：约数个数、阶乘分解。