题解 P1445 【[Violet]樱花】
P1445 [Violet]樱花
题目大意：
求：方程
\[\frac{1}{x}+\frac{1}{y}=\frac{1}{n!} \]的正整数解的组数，对 \(10^9+7\) 取模。
solution：
这种题当然得推一波柿子了：
\[\frac{x+y}{x\times y}=\frac{1}{n!} \]\[x\times y=n!\times (x+y) \]\[x\times y=n!\times x+n!\times y \]\[x\times y -n!\times y=n!\times x \]\[(x-n!)\times y=n!\times x \]\[y=\frac{x\times n!}{x-n!} \]我们把 \(x\) 那项 \(+n!\) 再 \(-n!\) ，显然结果不变：
\[y=\frac{(x-n!+n!)\times n!}{x-n!} \]打开括号，把 \(x-n!\) 看做一项， \(n!\) 看做另一项：
\[y=\frac{(x-n!)\times n!+(n!)^2}{x-n!} \]约分：
\[y=n!+\frac{(n!)^2}{x-n!} \]已知 \(x,y,n\) 都是正整数，所以当 \((x-n!)\mid (n!)^2\) 时，是一组合法解。所以问题就转化为求 \((n!)^2\) 的约数个数。
但问题又来了，平方很好解决，但是阶乘怎样处理呢？
我们把 \(n!\) 展开：\(1\times 2\times 3\times \cdots \times (n-1)\times n\)，假设现在试除质因数 \(3\) ，这里 \(3,6,9,\dots,3\times k\,\,\,(3\times k\leq n)\) 是 \(3^1\) 的倍数的数显然有 \(k\) 个，这里的 \(k_1=\lfloor\frac{n}{3^1}\rfloor\) ，\(n!\) 中就有 \(k_1\) 个质因子 \(3\) 。同理 \(3^2\) 的倍数有 \(k_2\lfloor\frac{n}{3^2}\rfloor\) 个， \(n!\) 中就又有 \(k_2\) 个质因子 \(3\) ，目前 \(n!\) 中有 \({k_1+k_2}\) 个 \(3\) 。由一般到普遍：在 \(n!\) 中质因子 \(p\) 的次数为：
\[c=\sum ^{p^i\leq n} _{i=1} \lfloor\frac{n}{p^i}\rfloor \]根据约数个数公式最后答案为：
\[\prod ^k _{i=1} (c_i\times 2 +1)\,\,\,\,\,\,\,\, (k \,为\, n\, 质因数个数) \]细节处理：
- 必要的地方开 \(LL\) 。
- 线性筛出质数会比正常分解快。
代码
#include
using namespace std;
typedef long long LL;
const int N=1e6+5,PR=8e5+5,mod=1e9+7;
bool vis[N];int pr[PR],cnt;
int n;
inline void xxs(){
for(int i=2;i<=n;i++){
if(!vis[i]) pr[++cnt]=i;
for(int j=1;j<=cnt;j++){
if(i*pr[j]>n) break;
vis[i*pr[j]]=1;
if(i%pr[j]==0) break;
}
}
}
int main(){
scanf("%d",&n);
xxs();
LL ans=1;
for(int i=1;i<=cnt;i++){
int res=0;
for(LL j=pr[i];j<=n;j*=pr[i]) res+=n/j;//注意这的LL
ans=ans*(res*2+1)%mod;//公式
}
printf("%lld",ans);
return 0;
}