题解：P9007 [入门赛 #9] 最澄澈的空与海 (Hard Version)

· · 题解

这题可不入门。

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

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

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

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

\dfrac{x-y}{z}&=\dfrac{\dfrac{y}{z}+n!-y}{z}\\ &=\dfrac{y+zn!-zy}{z^2}\\ &=\dfrac{n!}{n} \end{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。

(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 的情况呢？

\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;
}