P5221 Product 题解

· · 题解

来一个简单的 O(n) 解法：不用卡常，不用筛 \mu,\phi，不用整除分块。

只需要线性筛质数。

直接列式：

A=\prod_{i=1}^{n}\prod_{j=1}^n\frac{\text{lcm}(i,j)}{\gcd(i,j)}=\prod_{d=1}^n \prod_{i=1}^{\lfloor n/d\rfloor}\prod_{j=1}^{\lfloor n/d\rfloor}(ij)^{[gcd(i,j)=1]}

莫比乌斯反演一下。

A=\prod_{d=1}^n \prod_{i=1}^{\lfloor n/d\rfloor}\prod_{j=1}^{\lfloor n/d\rfloor}(ij)^{\sum_{s|i,s|j}\mu(s)}=\prod_{d=1}^n \prod_{i=1}^{\lfloor n/d\rfloor}\prod_{j=1}^{\lfloor n/d\rfloor}\prod_{s|i,s|j}(ij)^{\mu(s)}=\prod_{d=1}^n\prod_{s=1}^{\lfloor n / d \rfloor}\prod_{i=1}^{\lfloor n / ds \rfloor}\prod_{j=1}^{\lfloor n / ds \rfloor}(ijs^2)^{\mu(s)}=\prod_{d=1}^n\prod_{s=1}^{\lfloor n / d \rfloor}(\lfloor n / ds \rfloor !)^{2\mu(s)\lfloor n / ds \rfloor}s^{2\mu(s)\lfloor n / ds \rfloor^2}

为了方便我们对答案 A 先开个根，最后再平方回去。注意 t=ds。

\sqrt A=\prod_{d=1}^n\prod_{s=1}^{\lfloor n / d \rfloor}(\lfloor n / ds \rfloor !)^{\mu(s)\lfloor n / ds \rfloor}s^{\mu(s)\lfloor n / ds \rfloor^2}=\prod_{t=1}^n(\lfloor n / t \rfloor !)^{\lfloor n / t \rfloor \sum_{r|s}\mu(r)}(\prod_{s|t}s^{\mu(s)})^{\lfloor n / t \rfloor ^2}

注意到 \sum_{r|s}\mu(r)=[s=1]，我们把 t=1 和 t\geq 2 的情况分开。记数论函数 g(t)=\prod_{s|t}s^{\mu(s)}。

\sqrt A= (n!)^n\prod_{t=2}^n (g(t))^{\lfloor n / t \rfloor ^2}

由于用写出 t 的分解式后，可以用二项式定理简单证明如下性质，因此此处不加证明地直接给出此性质：

（原谅不会打大括号的 LaTeX）

若 t 可以表示为 p^k （p 为质数）的形式，则 g(t)=\frac{1}{p}；

否则 g(t)=1。

换句话说，我们只需要枚举所有能表示成 p^k 的 t 就行了。筛到某个质数 p 时，直接枚举 k 就行，把幂次累加并对 mod - 1 取模，只需求一次逆元和一次快速幂。设不大于 n 的质数个数为 \pi(n)，则这部分复杂度为 O(\pi(n)\log mod)。

线性筛的时候，只需要保存一个质数表，一个表示每个数是否为质数的 \text{bitset}。空间消耗不到 \text{1MB}，掉掉有余。

最终以 O(n+\pi(n)\log mod)=O(n+n\log mod/\log n)\approx O(n) 的时间复杂度解决了本题，可以认为是线性的。虽然推导过程中用到了莫比乌斯函数和其反演，但最终的式子非常简洁。

code：

#include <bits/stdc++.h>
const int mod = 104857601;
inline int mul(int x, int y){
    return (int)(1ll * x * y % (1ll * mod));
}
inline int add(int x, int y){
    return x + y >= mod ? x + y - mod : x + y;
}
inline int minus(int x, int y){
    return x < y ? x - y + mod : x - y;
}
inline int Qpow(int x, int y){
    int r = 1;
    while(y){
        if(y & 1) r = mul(r, x);
        x = mul(x, x);
        y >>= 1;
    }
    return r;
}
int n, ans = 1;
int p[100005], cnt = 0;
std::bitset <1000005> is;
void solve(){
    scanf("%d", &n);
    is.set();
    is[1] = 0;
    for(int i = 1; i <= n; ++i) ans = mul(ans, i);
    ans = Qpow(ans, n);
    for(int i = 2; i <= n; ++i){
        if(is[i] == 1){
            p[++cnt] = i;
            int q = i, t = Qpow(i, mod - 2);
            int s = 0;
            while(q <= n){
                s += 1ll * (n / q) * (n / q) % (mod - 1);
                s >= mod - 1 ? s -= (mod - 1) : true; 
                if(i <= 1000) q *= i;
                else break;
            }
            ans = mul(ans, Qpow(t, s));
        }
        for(int j = 1; j <= cnt && i * p[j] <= n; ++j){
            is[i * p[j]] = 0;
            if(i % p[j] == 0) break;
        }
    }
    printf("%d\n", mul(ans, ans));
    return ;
}
int main(){
    int T = 1;
    while(T--) solve();
    return 0;
}

后记：作者非常菜，完全不会做这道简单题，一直到 \sqrt A 之前的部分都是 @p31pr 完成的。