Product ,一道简单的 莫比乌斯反演 题目。
题目链接:Luogu P5221。
题目
题目描述
给定 \(n\),求
\[\prod^n _ {i=1}\prod^n _ {j=1}\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)}\pmod{104857601}\]
数据范围
变量 | 数据范围 |
---|---|
\(n\) | \(1\leq n\leq 10^6\) |
时空限制
题目编号 | 时间限制 | 空间限制 |
---|---|---|
Luogu P5221 | \(0.2\text{s}\) | \(8\text{MiB}\) |
题解
前置知识
- 莫比乌斯反演,可以看我的博客「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; }
近期评论