当前位置：首页 > news >正文

洛谷 P9007 [入门赛 #9] 最澄澈的空与海 (Hard Version)

news 来源：原创 2025/8/23 5:10:05

~~这道题可不入门。~~

$\color{blue}{\texttt{[Problem Discription]}}$

给定 $n$ ，求有多少组 $(x, y, z)$ 满足：

$x-\dfrac{y}{z}=n!$
$\dfrac{x-y}{z}=\dfrac{n!}{n}$

其中 $n!$ 表示 $n$ 的阶乘，即 $\prod\limits_{i=1}^{n} i$ 。 $x, y, z$ 为整数，可以是负整数。

多组询问。 $\leq T \leq 1 \times 10^{5},1 \leq n \leq 1 \times 10^{6}$ 。

$\color{blue}{\texttt{[Analysis]}}$

~~作为一个经历了高考摧残的人，最会干的事情就是化简冗长的式子。~~

干瞪眼看不出这两个式子有什么规律，变量太多了，因此考虑先消元。

由 $x-\dfrac{y}{z}=n!$ 得 $x=\dfrac{y}{z}+n!$ ，把它带入第二个式子中可得：

$\begin{aligned} \dfrac{x-y}{z}&=\dfrac{\dfrac{y}{z}+n!-y}{z}\\ &=\dfrac{y+zn!-zy}{z^2}\\ &=\dfrac{n!}{n} \end{aligned}$

通分，

$\begin{aligned} ny-nzn!-nzy&=n!z^2\\ n(z-1)y&=n!z(n-z)\\ y&=\dfrac{(n-1)!z(n-z)}{z-1} \end{aligned}$

因此，满足题意的 $(z - 1)$ 一定是 $(n - 1)! z (n - z)$ 的因数。除了 $z = 2$ 外， $(z - 1)$ 不会是 $z$ 的因数，且 $\gcd(z-1,z)=1$ ，因此 $(z - 1)$ 为 $(n - 1)! (n - z)$ 的因数。然而这个式子上下都含有 $z$ ，愚蠢的人脑是分析不出什么东西来的。

考虑引入新的参数 $k$ 。

$\begin{aligned} (n-1)!(n-z)&=k(z-1)\\ n!-(n-1)!z&=kz-k\\ \left [ (n-1)!+k\right ]z&=n!+k\\ z&=\dfrac{n!+k}{(n-1)!+k} \end{aligned}$

实话实说，这是一个非常美的式子，可惜它和上面一样，上下都含有 $k$ ，因此从难度上并没有变化。

思路貌似到这里就断了，怎么办？~~当然是看题解去（bushi）。~~

上面是把消去了 $x$ 保留 $y$ ，行不通的时候当然试试消去 $y$ 留下 $x$ 啦。

也不用重新计算，只需要把 $y$ 用 $z$ 表达的那个式子带入 $x$ 中，就可以得到：

$x=\dfrac{y}{z}+n!=\dfrac{(n-1)(n-1)!z}{z-1}$

同样， $\not = 2$ 时， $(z - 1)$ 不是 $z$ 的因数，因此 $(z - 1)$ 一定是 $(n - 1) (n - 1)!$ 的因数。 $z = 2$ 时， $z - 1 = 1$ 当然也是 $(n - 1) (n - 1)!$ 的因数。

因此问题转化为求 $(n - 1) (n - 1)!$ 的因数的个数。这个问题和原问题是等价的。记答案为 $\text{ans}(n)$ 。

为什么？

考虑 $(n - 1) (n - 1)!$ 的一个因数 $z$ ，带入上式就一定可以唯一的算出一个 $x (z), y (z)$ ， $x (z)$ 必然是一个整数。而 $y = z (x - n!)$ （由最开始的式子变形而来）在 $x, z$ 都是整数的情况下当然是整数。因此一个 $z$ 就唯一确定一组 $(x, y, z)$ ，而不同的 $z$ 确定的当然是不同的 $(x, y, z)$ 。两个问题的解构成一一映射。

根据因数个数定理，我们需要求的就是 $(n - 1) (n - 1)!$ 不同质因数出现的次数。

设每个质因数出现的次数为 $f(p_{i})$ 。答案即为 $\prod\limits_{i=1}^\text{prime count}\left (1+f(p_{i}) \right )$ 。

不能每次都重新求，考虑怎么从 $\text{ans}(n-1)$ 递推得到 $\text{ans}(n)$ 。

我们可以快速的将 $n$ 和 $(n - 1)$ 分解质因数，然后 $f(p_{i})$ 减去 $(n - 1)$ 的质因数出现次数，加上两倍的 $n$ 的质因数个数就行了（因为阶乘和阶乘前各有一个 $n$ ，所以是两倍）。

但是根号级别的分解质因数还是太慢了，能不能降低时间复杂度呢？

答案是可以的。如果我们知道 $n$ 的质因数都有谁，就不用一个一个数去实验了。当然不能把所有质因数都记下来（~~都记下来了还要试除法干嘛了~~），但是通过线性筛，我们可以顺便得到每个数的最小质因数是多少。每次除以最小质因数就可以大大加快算法了。

配合线性求逆元，程序跑得飞快。

还漏了一个问题，在上面那个式子中， $(z - 1)$ 是作为分母的，因此 $\not = 1$ 。有没有 $z = 1$ 的情况呢？

$z = 1$ 时有 $x-y=n!=\dfrac{n!}{n}$ ，因此 $n = 1$ 。因此只有 $n = 1$ 时答案为无穷。

$\color{blue}{\text{Code}}$

int f[N],n,T,ans[N];int prime[N],prcnt;
bool is_prime[N];
int minn_prime[N];
void get_prime(int n){for(int i=2;i<=n;i++)is_prime[i]=true;for(int i=2;i<=n;i++){if (is_prime[i]){minn_prime[i]=i;prime[++prcnt]=i;}for(int j=1;j<=prcnt;j++){if (1ll*i*prime[j]>n) break;is_prime[i*prime[j]]=false;minn_prime[i*prime[j]]=prime[j];if (i%prime[j]==0) break;}}
}int ksm(int a,int b){自己写快速幂
}int inv[N],fac[N];void init_inv(int n){fac[0]=1;for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;int tmp=ksm(fac[n],mod-2);inv[n]=1ll*fac[n-1]*tmp%mod;for(int i=n-1;i>=1;i--){tmp=1ll*tmp*(i+1)%mod;inv[i]=1ll*tmp*fac[i-1]%mod;}
}vector<pair<int,int> > prdiv;
void dp_init(int n){int cur=1;ans[0]=1;for(int i=1;i<=n;i++){prdiv.clear();int tmp=i;while (tmp!=1){int cnt=0,div=minn_prime[tmp];while (tmp%div==0){tmp/=div;cnt++;}prdiv.push_back(make_pair(div,cnt));}tmp=prdiv.size();for(int j=0;j<tmp;j++){int val=prdiv[j].first,cnt=prdiv[j].second;cur=1ll*cur*inv[1+f[val]]%mod;f[val]+=(cnt<<1);cur=1ll*cur*(1+f[val])%mod;}ans[i]=cur;for(int j=0;j<tmp;j++){int val=prdiv[j].first,cnt=prdiv[j].second;cur=1ll*cur*inv[1+f[val]]%mod;f[val]-=cnt;cur=1ll*cur*(1+f[val])%mod;}}
}int main(){get_prime(1e6);init_inv(1e6);dp_init(1e6);T=read();for(int Case=1;Case<=T;Case++){n=read();if (n==1) printf("inf\n");else printf("%d\n",ans[n-1]);}return 0;
}

相关文章：