ACWing 1294 樱花题解

y0k1n0

2025 年 05 月 15 日

23 次浏览

暂无评论

1061字数

数论

# ACWing 1294 樱花 题解

## 题目描述

给定一个整数 $n$，求有多少正整数数对 $(x,y)$ 满足 $\frac{1}{x} + \frac{1}{y} = \frac{1}{n!}$。

## 输入格式

一个整数 $n$。

## 输出格式

一个整数，表示满足条件的数对数量。

答案对 $10^9+7$ 取模。

## 解题思路

首先观察上面的公式：$\frac{1}{x} + \frac{1}{y} = \frac{1}{n!}$, 可以看到公式中只有两个变量$x$, $y$，因此$y$一定可以由$x$表示得到， 又有$x,y\in N^*$， 因此确定了$x$的取值， 如果对应的$y$是整数， 即找到一个数对。

因此可以先对上面的公式进行变形， 将$y$写作$x$的表达式：

$$
\begin{align}
\frac{xy}{x + y} &= n! \\
xn! &= y(x-n!) \\
y &= \frac{xn!}{x-n!} \\
y &= n! + \frac{(n!)^2}{x-n!}
\end{align}
$$

又上式可以看出， 只要分母$x-n!$是$(n!)^2$的约数， 则$x,y$均是整数， 因此这道题只需要求出$(n!)^2$的所有约数即可。

设$n = p_1^{a_1} \cdot p_2^{a_2}\cdots p_k^{a_k}$, 则$n$的约数的个数为$(a_1 + 1)\times (a_2 + 1)\times \cdots \times (a_k + 1)$

## AC代码

```cpp
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
typedef long long LL;

int n;
LL ans = 1;
int primes[N], cnt;
bool st[N];
void get_primes(int n){
    for(int i = 2; i <= n; i ++){
        if(!st[i]) primes[++ cnt] = i;
        for(int j = 1; primes[j] <= n / i; j ++){
            st[i * primes[j]] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
    cin >> n;
    get_primes(n);

for(int i = 1; i <= cnt; i ++){
        LL res = 0;
        for(int j = n; j; j /= primes[i]){
            res += j / primes[i];
        }
        ans = (ans * (2 * res + 1)) % mod;
    }

cout << ans << endl;
	return 0;
}
```

最后修改：2025 年 05 月 15 日