126 lines
3.4 KiB
Markdown
126 lines
3.4 KiB
Markdown
##[$AcWing$ $1294$. 樱花](https://www.acwing.com/problem/content/1296/)
|
||
|
||
### 一、题目描述
|
||
给定一个整数 $n$，求有多少正整数数对 $(x,y)$ 满足 $\large \frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$
|
||
|
||
**输入格式**
|
||
一个整数 $n$。
|
||
|
||
**输出格式**
|
||
一个整数，表示满足条件的数对数量。
|
||
|
||
答案对 $10^9+7$ 取模。
|
||
|
||
**数据范围**
|
||
$1≤n≤10^6$
|
||
|
||
**输入样例**
|
||
```cpp {.line-numbers}
|
||
2
|
||
```
|
||
**输出样例**
|
||
```cpp {.line-numbers}
|
||
3
|
||
```
|
||
**样例解释**
|
||
共有三个数对 $(x,y)$ 满足条件，分别是 $(3,6),(4,4),(6,3)$。
|
||
|
||
|
||
### 二、解题思路
|
||
做了这题，感觉这类题目的大多数分析过程都是这样的:
|
||
* 求有多少对整数对$(x,y)$满足一条方程，则方程一定存在解，将$y$转换为关于$x$的表示式，再根据$y$的约数条件，求出$(x,y)$的匹配数，即一个$x$对应一个$y$
|
||
|
||
#### 1、确定$x,y$范围
|
||
$$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$$
|
||
∵$x,y∈Z^+$
|
||
∴$x>n!$ $y>n!$ 小学数学知识~
|
||
#### 2、推表达式
|
||
转换为$y$的表示式
|
||
$$\frac{x+y}{xy}=\frac{1}{n!}$$
|
||
变形
|
||
$$xn!+yn!=xy$$
|
||
继续变形
|
||
$$xn!=y(x-n!)$$
|
||
$$y=\frac{xn!}{x-n!}$$
|
||
<font color='red' size=4><b>经典的变形技巧：</b></font>
|
||
$$y=\frac{(x-n!+n!)n!}{x-n!}$$
|
||
$$y=\frac{(x-n!)n!+n!^2}{x-n!}$$
|
||
$$y=n! + \frac{n!^2}{x-n!}$$
|
||
|
||
因为上面已经证明了$x-n!>0$的，所以要想$y$有正整数解，则必然需要
|
||
$$(x-n!)|n!^2$$
|
||
|
||
换句话说，就是$n!^2$有多少个约数，就有相应的正整数$x$,也就有一个对应的$y$。
|
||
如果我们能够求得$n!^2$的约数个数，也就是${x,y}$的匹配对数。
|
||
|
||
#### 3、阶乘分解质因数
|
||
参考 [$Acwing197$. 阶乘分解](https://www.cnblogs.com/littlehb/p/16283654.html) 的方法
|
||
|
||
* 先筛出$n$以内的质数
|
||
* 计算每个质数因子出现的次数
|
||
```c++
|
||
for (int i = 0; i < cnt; i++) {
|
||
int p = primes[i];
|
||
int s = 0;
|
||
for (int j = n; j; j /= p) s += j / p;
|
||
printf("%d %d\n", p, s);
|
||
}
|
||
```
|
||
|
||
#### 4、约数个数
|
||
求$n!^2$一共有多少个约数
|
||
假设$$n!=P_1^{c_1} \times P_2^{c_2}\times ...\times P_k^{c_k}$$
|
||
则$$n!^2=P_1^{2c_1}\times P_2^{2c_2}\times ...\times P_k^{2c_k}$$
|
||
|
||
根据<font color='red'><b>约数个数定理</b></font>
|
||
知道约数的个数是$(2c_1+1)\times (2c_2+1)\times …\times (2c_k+1)$
|
||
|
||
#### 5、时间复杂度 $O(n)$
|
||
|
||
### 三、实现代码
|
||
```cpp {.line-numbers}
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
#define int long long
|
||
#define endl '\n'
|
||
const int MOD = 1e9 + 7;
|
||
|
||
// 欧拉筛
|
||
const int N = 1e6 + 10;
|
||
int primes[N], cnt; // primes[]存储所有素数
|
||
bool st[N]; // st[x]存储x是否被筛掉
|
||
void get_primes(int n) {
|
||
memset(st, 0, sizeof st);
|
||
cnt = 0;
|
||
for (int i = 2; i <= n; i++) {
|
||
if (!st[i]) primes[cnt++] = i;
|
||
for (int j = 0; primes[j] * i <= n; j++) {
|
||
st[primes[j] * i] = true;
|
||
if (i % primes[j] == 0) break;
|
||
}
|
||
}
|
||
}
|
||
|
||
signed main() {
|
||
int n;
|
||
cin >> n;
|
||
|
||
// 步骤1:筛质数
|
||
get_primes(n);
|
||
|
||
// 步骤2：阶乘质因子分解
|
||
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;
|
||
|
||
// 步骤3：约数个数公式
|
||
res = res * (2 * s + 1) % MOD;
|
||
}
|
||
cout << res << endl;
|
||
}
|
||
|
||
```
|
||
|
||
|