「Violet5」樱花
[Violet5]樱花题解
题意概括：
题目意思很明白，输入一个\(int\)类型整数\(n\) ( \(1<=n<=10^6\) ) 求方程 \(\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}\) ( \(n!\) 表示 \(n\) 的阶乘，即 \(n!=1\times2\times3\times······\times n\) ) 解的个数
题目分析：
肯定是一个数论题(废话)，题目中的方程直接枚举是 \(O(n^3)\) 的时间复杂度，绝对会 \(TLE\) ，那么就只能用魔法打败魔法，用math知识对方程进行分析：
\[\begin{aligned}
& \frac{1}{x} + \frac{1}{y} = \frac{1}{n!}\\
& 设 n!=k，\\
\end{aligned}
\]
第一眼看上去，\(x\) 和 \(y\) 都是一次的整数，只有 \(n!\) 是一个式子，所以用一个未知数代替，方便运算和思考。其实就是我懒对原方程进行化简，我习惯把 \(x\) 当作主元，用 \(y\) 也可以。把 \(y\) 和 \(k\) 当作一个常数，用解普通方程的步骤去解。
\[\begin{aligned}
& \therefore \frac{1}{x} + \frac{1}{y} = \frac{1}{k}\\
& \frac{1}{x} = \frac{1}{k} - \frac{1}{y}\\
& \frac{1}{x} = \frac{y}{ky} - \frac{k}{ky}\\
& \frac{1}{x} = \frac{y-k}{ky}\\
& x = \frac{ky}{y-k}\\
\end{aligned}
\]
这时，无法对方程继续化简，但分式上下都有 \(y\) 和 \(k\) ，所以可以考虑再设一个关于 \(y\) 和 \(k\) 的未知数，去表达 \(y\) 和 \(k\) 的关系。
\[\begin{aligned}
& 设 y-k = p，\\
& \therefore y = k + p\\
\end{aligned}
\]
找到之后，就可以把 \(y=k+p\) 代入方程，得到
\[\begin{aligned}
& \therefore x = \frac{k(k+p)}{p}\\
& \therefore x = k+\frac{k^2}{p}\\
\end{aligned}
\]
解出 \(x\) 的值后，观察式子，发现可以运用文化课上讲过的整数的性质，
\[\begin{aligned}
& \because x，k=n!为正整数\\
& \therefore p \mid k^2\\
& \therefore y-n! \mid (n!)^2\\
& \therefore (y-n!) 为(n!)^2的因子\\
& \therefore (y-n!) 为n!的因子\\
& \because y，n!为正整数\\
& \therefore x为正整数\\
& \therefore 只要(y-n!)为n!的因子，就有原方程的一组解\\
\end{aligned}
\]
通过分析，就可以把原问题转化为求\(n!\)的因子数
代码实现
由唯一分解定理，我们只需要解出n!的质因数，balabala的一个埃氏筛函数
int primes[1000005];//记录质因数
bool st[1000005];//标记是否为质数
int cnt;
int n;
long long ans=1;
void prime_set(int n){
st[1]=1;
for (int i=2;i<=n;i++){
if (!st[i])
primes[++cnt]=i;
for (int j=1;j<=cnt&&primes[j]*i<=n;j++){
st[primes[j]*i]=1;
if (i%primes[j]==0){
break;
}
}
}
}
通过唯一分解定理的另一个公式，即
\(n的因子数=\prod\limits_{i=0}^{质因子个数}质因子i的个数+1\)
就可以得到答案了
prime_set(n);
for (int i = 1; i <= cnt; i++){
int s = 0;
for (int j=n;j;j/=primes[i]){
s+=j/primes[i];
}
ans=1ll*ans*(s<<1|1)%P;//1ll用来防止数据溢出
}
printf("%lld",ans);
Code
#include<bits/stdc++.h>
#define P 1000000007
using namespace std;
int primes[1000005];
bool st[1000005];
int cnt;
int n;
long long ans=1;
void prime_set(int n){
st[1]=1;
for (int i=2;i<=n;i++){
if (!st[i])
primes[++cnt]=i;
for (int j=1;j<=cnt&&primes[j]*i<=n;j++){
st[primes[j]*i]=1;
if (i%primes[j]==0){
break;
}
}
}
}
int main(){
scanf("%d",&n);
prime_set(n);
for (int i = 1; i <= cnt; i++){
int s = 0;
for (int j=n;j;j/=primes[i]){
s+=j/primes[i];
}
ans=1ll*ans*(s<<1|1)%P;
}
printf("%lld",ans);
return 0;
}