专栏文章
题解：P9007 [入门赛 #9] 最澄澈的空与海 (Hard Version)
P9007题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mipefvcd
- 此快照首次捕获于
- 2025/12/03 10:40 3 个月前
- 此快照最后确认于
- 2025/12/03 10:40 3 个月前
这题可不入门。
干瞪眼看不出这两个式子有什么规律，变量太多了，因此考虑先消元。
由 得 ，把它带入第二个式子中可得：
\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}$$
同样，$z \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)$ 是作为分母的，因此 $z \not = 1$。有没有 $z=1$ 的情况呢？
>
> - $z=1$ 时有 $x-y=n!=\dfrac{n!}{n}$，因此 $n=1$。因此只有 $n=1$ 时答案为无穷。
$\color{blue}{\text{Code}}$
```cpp
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;
}
```相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...