AcWing 1294. 樱花 题解

题目传送门

题意简述

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

\(\texttt{SOLUTION}\)

看到这种题目，第一眼想到的一定是推柿子。

很显然可以推出：\(xy=n!\times x+n!\times y\) 。
把 \(x\) 放一边 \(y\) 放一边可得：\(x=\frac{n!y}{y-n!}\) 。
右边上下都有 \(y\) 很烦人，去掉得：\(x=\frac{n!^2}{y-n!}+n!\) 。
由于 \(x\) 固定了， \(y\) 也固定了。
所以只需要求 \(x\) 的取值个数了。
又 \(\because x,n!\in \mathbb{N}^+\)。
\(\therefore \frac{n!^2}{y-n!}\in \mathbb{N}^+\)。
\(\therefore {y-n!}\mid n!^2\)。
又易得 \(y>n!\)。
\(\therefore y-n!>0\)。
\(\therefore y\text{的取值个数即为} n!^2 \text{的因数个数}\)。

于是只要求 \(n!^2\) 的因数个数即可。

这就很 \(\texttt{easy}\) 了。

代码呢？也咕咕咕着了。