「题解」Product

Product ，一道简单的 莫比乌斯反演 题目。

题目链接：Luogu P5221。

题目

题目描述

给定 \(n\)，求
\[\prod^n _ {i=1}\prod^n _ {j=1}\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)}\pmod{104857601}\]

数据范围

时空限制

题解

前置知识

• 莫比乌斯反演，可以看我的博客「OI」莫比乌斯反演。

思路

\[
\begin{aligned}
\texttt{ans}&\equiv\prod^n _ {i=1}\prod^n _ {j=1}\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)}\pmod{104857601}\\
&\equiv\prod^n _ {i=1}\prod^n _ {j=1}\frac{(\frac{ij}{\gcd(i,j)})}{\gcd(i,j)}\\
&\equiv\prod^n _ {i=1}\prod^n _ {j=1}\frac{ij}{\gcd^2(i,j)}\\
&\equiv\prod^n _ {i=1}i^n\prod^n _ {j=1}\frac{j}{\gcd^2(i,j)}\\
&\equiv\prod^n _ {i=1}i^n\times n!\times \prod^n _ {j=1}\frac{1}{\gcd^2(i,j)}\\
&\equiv\frac{(n!)^{2n}}{\prod^n _ {i=1}\prod^n _ {j=1}\gcd^2(i,j)}\\
&\equiv\frac{(n!)^{2n}}{(\prod^n _ {i=1}\prod^n _ {j=1}\gcd(i,j))^2}\\
&\equiv\frac{(n!)^{2n}}{\prod^n _ {d=1}d^{\sum^{\lfloor\frac{n}{d}\rfloor} _ {i=1}\sum^{\lfloor\frac{n}{d}\rfloor} _ {j=1}[\gcd(i,j)=1]}}\\
&\equiv\frac{(n!)^{2n}}{\prod^n _ {d=1}d^{2\sum^{\lfloor\frac{n}{d}\rfloor} _ {i=1}\sum^i _ {j=1}[\gcd(i,j)=1]}}\\
&\equiv\frac{(n!)^{2n}}{\prod^n _ {d=1}d^{(2\sum^{\lfloor\frac{n}{d}\rfloor} _ {i=1}\varphi(i))-1}}\\
&\equiv\frac{(n!)^{2n}}{\prod^n _ {d=1}d^{(2\sum^{\lfloor\frac{n}{d}\rfloor} _ {i=1}\varphi(i))-1\pmod{\varphi(104857601)}}}\pmod{104857601}
\end{aligned}
\]

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define MOD 104857601

const int MAXN=1000000+5;
const int MAXSIZE=1000000+5;

inline int pow(reg int x,reg int exp,reg int mod){
    reg int res=1;
    while(exp){
        if(exp&1)
            res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        exp>>=1;
    }
    return res;
}

inline int inv(reg int x,reg int mod){
    return pow(x,mod-2,mod);
}

bitset<MAXSIZE> vis;
int tot,prime[80000];
int phi[MAXSIZE];

inline void Init(reg int n){
    phi[1]=1;
    for(reg int i=2;i<=n;++i){
        if(!vis[i]){
            prime[++tot]=i;
            phi[i]=i-1;
        }
        for(reg int j=1;j<=tot&&i*prime[j]<=n;++j){
            vis[i*prime[j]]=true;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
    return;
}

int n;

int main(void){
    scanf("%d",&n);
    Init(n);
    for(reg int i=1;i<=n;++i)
        phi[i]=(0ll+phi[i-1]+2ll*phi[i])%(MOD-1);
    reg int ans1=1;
    for(reg int i=1;i<=n;++i)
        ans1=1ll*ans1*i%MOD;
    ans1=pow(ans1,2*n,MOD);
    reg int ans2=1;
    for(reg int i=2;i<=n;++i)
        ans2=1ll*ans2*pow(i,phi[n/i]-1,MOD)%MOD;
    printf("%lld\n",1ll*ans1*inv(1ll*ans2*ans2%MOD,MOD)%MOD);
    return 0;
}