Möbius Inversion tasks: Solution Set
Rigel
·
2026-09-28 15:21:26
·
算法·理论
List of Möbius Inversion tasks
对这篇深度好文的拙略模仿。
如无特殊说明，本文中每道题的答案均记为 \mathrm{Ans} 。
SP26017 GCDMAT - GCD OF MATRIX
GCDMAT
Formerly: \,\small\textbf{\textsf{\textcolor{9C3DCF}{省选/NOI−}}}
Now: \,\small\textbf{\textsf{\textcolor{3498DB}{提高+/省选−}}}
给定 a,b,c,d ，求：
\left( \sum\limits_{i = a}^{c} \sum\limits_{j = b}^{d} \gcd(i,j) \right) \bmod (10^9 + 7).
多测，T 组数据，1 \le T \le 500 ，1 \le a,b,c,d \le 5 \times 10^4 ，a \le c ，b \le d 。
推导过程中忽略取模。
:::info[法一]{open}
设：
F(n,m) = \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \gcd(i,j).
则：
\mathrm{Ans} = F(c,d) - F(a-1,d) - F(c,b-1) + F(a-1,b-1).
考虑 F(n,m) 。
显然 F(n,m) = F(m,n) 。于是问题归约至 n \le m 的情形。
枚举 \gcd ：
F(n,m) = \sum\limits_{k = 1}^{n} k \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \left[ \gcd(i,j) = k \right].
令 p = \dfrac{i}{k} ，q = \dfrac{j}{k} ：
F(n,m) &= \sum\limits_{k = 1}^{n} k \sum\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} \left[ \gcd(p,q) = 1 \right]\\
&= \sum\limits_{k = 1}^{n} k \sum\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} \sum\limits_{d \mid \gcd(p,q)} \mu(d)\\
&= \sum\limits_{k = 1}^{n} k \sum\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} \sum\limits_{\substack{d \mid p \\ d \mid q}} \mu(d)\\
&= \sum\limits_{k = 1}^{n} k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \mu(d) \sum\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} [d \mid p] \sum\limits_{q = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} [d \mid q]\\
&= \sum\limits_{k = 1}^{n} k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \mu(d) \left\lfloor \frac{n}{kd} \right\rfloor \left\lfloor \frac{m}{kd} \right\rfloor.
\end{aligned}
令 t = kd ，则 d = \dfrac{t}{k} ：
F(n,m) &= \sum\limits_{k = 1}^{n} k \sum\limits_{\substack{t = 1 \\ k \mid t}}^{n} \mu \left( \frac{t}{k} \right) \left\lfloor \frac{n}{t} \right\rfloor \left\lfloor \frac{m}{t} \right\rfloor\\
&= \sum\limits_{t = 1}^{n} \sum\limits_{k \mid t} k \cdot \mu \left( \frac{t}{k} \right) \left\lfloor \frac{n}{t} \right\rfloor \left\lfloor \frac{m}{t} \right\rfloor.
\end{aligned}
由 \operatorname{id} * \,\mu = \varphi ：
F(n,m) = \sum\limits_{t = 1}^{n} \varphi(t) \left\lfloor \frac{n}{t} \right\rfloor \left\lfloor \frac{m}{t} \right\rfloor.
:::
:::info[法二]{open}
考虑：
F(n,m) = \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \gcd(i,j).
由 \operatorname{id} = \varphi * \mathbf{1} ：
F(n,m) &= \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \sum\limits_{d \mid \gcd(i,j)} \varphi(d)\\
&= \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \sum\limits_{\substack{d \mid i \\ d \mid j}} \varphi(d)\\
&= \sum\limits_{d = 1}^{n} \varphi(d) \sum\limits_{i = 1}^{n} [d \mid i] \sum\limits_{j = 1}^{m} [d \mid j]\\
&= \sum\limits_{d = 1}^{n} \varphi(d) \left\lfloor \frac{n}{d} \right\rfloor \left\lfloor \frac{m}{d} \right\rfloor.
\end{aligned}
:::
预处理出 \varphi 的前缀和后数论分块即可。
设 n 与 a,b,c,d 同阶，则时间复杂度为 \mathcal{O}\left( n + T \sqrt{n} \right) 。
:::info[Code]
#include<bits/stdc++.h>
#define int long long
const int N=5e4+10;
const int TT=1e9+7;
using namespace std;
int T;
int _n=5e4;
int a,b,c,d,ans;
int phi[N];
int cnt,p[N];
bool vis[N];
inline int read(){
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
return ret*f;
}
void _init(){
phi[1]=1;
for(int i=2;i<=_n;i++){
if(!vis[i]){
p[++cnt]=i;
phi[i]=i-1;
}
for(int j=1;j<=cnt&&i*p[j]<=_n;j++){
vis[i*p[j]]=1;
if(i%p[j]){
phi[i*p[j]]=phi[i]*(p[j]-1);
}else{
phi[i*p[j]]=phi[i]*p[j];
break;
}
}
}
for(int i=1;i<=_n;i++)phi[i]=(phi[i]+phi[i-1])%TT;
}
int F(int n,int m){
if(n>m)swap(n,m);
int ret=0;
for(int l=1,r;l<=n;l=r+1){
r=min(n/(n/l),m/(m/l));
ret+=((phi[r]-phi[l-1])%TT+TT)%TT*(n/l)%TT*(m/l)%TT;
ret%=TT;
}
return ret;
}
void _solve(){
a=read(),b=read(),c=read(),d=read();
ans=F(c,d)-F(a-1,d)-F(c,b-1)+F(a-1,b-1);
ans=(ans%TT+TT)%TT;
printf("%lld\n",ans);
}
signed main(){
_init();
T=read();
read(),read();
while(T--)_solve();
return 0;
}:::
P1829 [集训队互测 2010] Crash的数字表格 / JZPTAB
JZPTAB
\small\textbf{\textsf{\textcolor{9C3DCF}{省选/NOI−}}}
给定 n,m ，求：
\left( \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \operatorname{lcm}(i,j) \right) \bmod 20101009.
同样忽略取模，并将问题归约至 n \le m 的情形。
套路地推式子：
\mathrm{Ans} &= \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \frac{ij}{\gcd(i,j)}\\
&= \sum\limits_{k = 1}^{n} \frac{1}{k} \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} [\gcd(i,j)=k] ij\\
&= \sum\limits_{k = 1}^{n} \frac{1}{k} \sum\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} [\gcd(p,q)=1] k^2 pq\\
&= \sum\limits_{k = 1}^{n} k \sum\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} pq \sum\limits_{d \mid \gcd(p,q)} \mu(d)\\
&= \sum\limits_{k = 1}^{n} k \sum\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} pq \sum\limits_{\substack{d \mid p \\d \mid q}} \mu(d)\\
&= \sum\limits_{k = 1}^{n} k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \mu(d) \sum\limits_{\substack{p = 1 \\ d \mid p}}^{\left\lfloor \frac{n}{k} \right\rfloor} p \sum\limits_{\substack{q = 1 \\ d \mid q}}^{\left\lfloor \frac{m}{k} \right\rfloor} q.
\end{aligned}
令 p = ud ，q = vd ：
\mathrm{Ans} &= \sum\limits_{k = 1}^{n} k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \mu(d) \sum\limits_{u = 1}^{\left\lfloor \frac{n}{kd} \right\rfloor} ud \sum\limits_{v = 1}^{\left\lfloor \frac{m}{kd} \right\rfloor} vd\\
&= \sum\limits_{k = 1}^{n} k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} d^2 \mu(d) \sum\limits_{u = 1}^{\left\lfloor \frac{n}{kd} \right\rfloor} u \sum\limits_{v = 1}^{\left\lfloor \frac{m}{kd} \right\rfloor} v.
\end{aligned}
令 G(n) = \displaystyle{\sum\limits_{i = 1}^{n} i} = \dfrac{n (n + 1)}{2} ：
\mathrm{Ans} = \sum\limits_{k = 1}^{n} k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} d^2 \mu(d) G\left( \left\lfloor \frac{n}{kd} \right\rfloor \right) G\left( \left\lfloor \frac{m}{kd} \right\rfloor \right).
套路地，令 t = kd ：
\mathrm{Ans} &= \sum\limits_{k = 1}^{n} k \sum\limits_{\substack{t = 1 \\ k \mid t}}^{n} \left( \frac{t}{k} \right)^2 \mu \left( \frac{t}{k} \right) G\left( \left\lfloor \frac{n}{t} \right\rfloor \right) G\left( \left\lfloor \frac{m}{t} \right\rfloor \right)\\
&= \sum\limits_{t = 1}^{n} \sum\limits_{k \mid t} k \left( \frac{t}{k} \right)^2 \mu \left( \frac{t}{k} \right) G\left( \left\lfloor \frac{n}{t} \right\rfloor \right) G\left( \left\lfloor \frac{m}{t} \right\rfloor \right)\\
&= \sum\limits_{t = 1}^{n} \sum\limits_{d \mid t} \frac{t}{d} \cdot d^2 \mu(d) G\left( \left\lfloor \frac{n}{t} \right\rfloor \right) G\left( \left\lfloor \frac{m}{t} \right\rfloor \right)\\
&= \sum\limits_{t = 1}^{n} t \sum\limits_{d \mid t} d \cdot \mu (d) G\left( \left\lfloor \frac{n}{t} \right\rfloor \right) G\left( \left\lfloor \frac{m}{t} \right\rfloor \right).\\
\end{aligned}
令 F(n) = \displaystyle{\sum\limits_{d \mid n} d \cdot \mu(d)} ：
\mathrm{Ans} = \sum\limits_{t = 1}^{n} t \cdot F(t) G\left( \left\lfloor \frac{n}{t} \right\rfloor \right) G\left( \left\lfloor \frac{m}{t} \right\rfloor \right).
显然 F 为积性函数。
线性筛出 F 并预处理出 t \cdot F(t) 的前缀和后数论分块即可。
时间复杂度（视 n,m 同阶）：预处理 \mathcal{O}(n) ，数论分块 \mathcal{O}(\sqrt{n}) ，总复杂度 \mathcal{O}(n) 。如果是多组数据的话可以做到 \mathcal{O}(n + T \sqrt{n}) 。
:::info[如何线性筛出 F ？]{open}
考虑 F(p^c) 的取值，其中 p 为质数：
F(p^c) &= \sum\limits_{d \mid p^c} d \cdot \mu(d)\\
&= \sum\limits_{i = 0}^{c} p^i \cdot\mu(p^i)\\
&= 1 \cdot \mu(1) + p \cdot \mu(p)\\
&= -p + 1.
\end{aligned}
考虑线性筛的过程。
设当前用 i 和 p_j 筛去了 x = i \cdot p_j 。显然 \operatorname{lpf}(x) = p_j 。
F(x) &= F(i) F(p_j)\\
&= F(i) \cdot (- p_j + 1).
\end{aligned}
当 p_j \mid i 时，设 i = p_j^c \cdot k ：
F(x) &= F(k) F(p_j^{c + 1})\\
&= \frac{F(i)}{F(p_j^c)} \cdot F(p_j^{c + 1})\\
&= F(i).
\end{aligned}
:::
:::info[Code]
#include<bits/stdc++.h>
#define int long long
const int N=1e7+10;
const int TT=20101009;
using namespace std;
int n,m,ans;
int F[N];
int cnt,p[N];
bool vis[N];
inline int read(){
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
return ret*f;
}
void _init(){
F[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i]){
p[++cnt]=i;
F[i]=-i+1;
}
for(int j=1;j<=cnt&&i*p[j]<=n;j++){
vis[i*p[j]]=1;
if(i%p[j]){
F[i*p[j]]=F[i]*(-p[j]+1);
}else{
F[i*p[j]]=F[i];
break;
}
}
}
for(int i=1;i<=n;i++)F[i]=((F[i]%TT+TT)%TT*i%TT+F[i-1])%TT;
}
int G(int n){
return n*(n+1)/2%TT;
}
signed main(){
n=read(),m=read();
if(n>m)swap(n,m);
_init();
for(int l=1,r;l<=n;l=r+1){
r=min(n/(n/l),m/(m/l));
ans+=((F[r]-F[l-1])%TT+TT)%TT*G(n/l)%TT*G(m/l)%TT;
ans%=TT;
}
printf("%lld\n",ans);
return 0;
}:::
P3911 最小公倍数之和
最小公倍数之和
Formerly: \,\small\textbf{\textsf{\textcolor{9C3DCF}{省选/NOI−}}}
Now: \,\small\textbf{\textsf{\textcolor{13C2C2}{提高}}}
给定一个长为 N 的序列 A_1 \sim A_N ，求：
\sum\limits_{i = 1}^{N} \sum\limits_{j = 1}^{N} \operatorname{lcm}(A_i,A_j).
令 n = \max_{i=1}^{N} A_i ：
\mathrm{Ans} &= \sum\limits_{i = 1}^{N} \sum\limits_{j = 1}^{N} \sum\limits_{x = 1}^{n} \sum\limits_{y = 1}^{n} [A_i = x] [A_j = y] \operatorname{lcm}(x,y)\\
&= \sum\limits_{x = 1}^{n} \sum\limits_{y = 1}^{n} \sum\limits_{i = 1}^{N} [A_i = x] \sum\limits_{j = 1}^{N} [A_j = y] \operatorname{lcm}(x,y).
\end{aligned}
令 c(x) = \displaystyle{\sum\limits_{i = 1}^{N} [A_i = x]} ：
\mathrm{Ans} &= \sum\limits_{x = 1}^{n} \sum\limits_{y = 1}^{n} c(x) c(y) \operatorname{lcm}(x,y)\\
&= \sum\limits_{x = 1}^{n} \sum\limits_{y = 1}^{n} c(x) c(y) \frac{xy}{\gcd(x,y)}\\
&= \sum\limits_{k = 1}^{n} \frac{1}{k} \sum\limits_{x = 1}^{n} \sum\limits_{y = 1}^{n} [\gcd(x,y) = k] c(x) c(y) xy\\
&= \sum\limits_{k = 1}^{n} \frac{1}{k} \sum\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} [\gcd(p,q) = 1] c(kp) c(kq) k^2 pq\\
&= \sum\limits_{k = 1}^{n} k \sum\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} c(kp) c(kq) pq \sum\limits_{d \mid \gcd(p,q)} \mu(d)\\
&= \sum\limits_{k = 1}^{n} k \sum\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} c(kp) c(kq) pq \sum\limits_{\substack{d \mid p \\d \mid q}} \mu(d)\\
&= \sum\limits_{k = 1}^{n} k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \mu(d) \sum\limits_{\substack{p = 1 \\ d \mid p}}^{\left\lfloor \frac{n}{k} \right\rfloor} p \cdot c(kp) \sum\limits_{\substack{q = 1 \\ d \mid q}}^{\left\lfloor \frac{n}{k} \right\rfloor} q \cdot c(kq)\\
&= \sum\limits_{k = 1}^{n} k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \mu(d) \sum\limits_{u = 1}^{\left\lfloor \frac{n}{kd} \right\rfloor} du \cdot c(kdu) \sum\limits_{v = 1}^{\left\lfloor \frac{n}{kd} \right\rfloor} dv \cdot c(kdv)\\
&= \sum\limits_{k = 1}^{n} k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} d^2 \mu(d) \sum\limits_{u = 1}^{\left\lfloor \frac{n}{kd} \right\rfloor} u \cdot c(kdu) \sum\limits_{v = 1}^{\left\lfloor \frac{n}{kd} \right\rfloor} v \cdot c(kdv)\\
&= \sum\limits_{k = 1}^{n} k \sum\limits_{\substack{t = 1 \\ k \mid t}}^{n} \left( \frac{t}{k} \right)^2 \mu \left( \frac{t}{k} \right) \sum\limits_{u = 1}^{\left\lfloor \frac{n}{t} \right\rfloor} u \cdot c(tu) \sum\limits_{v = 1}^{\left\lfloor \frac{n}{t} \right\rfloor} v \cdot c(tv).
\end{aligned}
令 G(x) = \displaystyle{\sum\limits_{i = 1}^{\left\lfloor \frac{n}{x} \right\rfloor}i \cdot c(xi)} ：
\mathrm{Ans} &= \sum\limits_{k = 1}^{n} k \sum\limits_{\substack{t = 1 \\ k \mid t}}^{n} \left( \frac{t}{k} \right)^2 \mu \left( \frac{t}{k} \right) \left( G(t) \right) ^2\\
&= \sum\limits_{t = 1}^{n} \sum\limits_{k \mid t} k \left( \frac{t}{k} \right)^2 \mu \left( \frac{t}{k} \right) \left( G(t) \right) ^2\\
&= \sum\limits_{t = 1}^{n} \sum\limits_{d \mid t} \frac{t}{d} \cdot d^2 \mu(d) \left( G(t) \right) ^2\\
&= \sum\limits_{t = 1}^{n} t \sum\limits_{d \mid t} d \cdot \mu(d) \left( G(t) \right) ^2.
\end{aligned}
令 F(x) = \displaystyle{\sum\limits_{d \mid x} d \cdot \mu(d)} ：
\mathrm{Ans} = \sum\limits_{t = 1}^{n} t \cdot F(t) \left( G(t) \right) ^2.
时间复杂度：
$$\begin{aligned}
T(n) &= \mathcal{O}(n) + \sum\limits_{i = 1}^{n} \mathcal{O} \left( \frac{n}{i} \right)\\
&= \mathcal{O} \left( \int_{1}^{n} \frac{n}{x}\, \mathrm{d} x \right)\\
&= \mathcal{O}(n \log n).
\end{aligned}$$
:::info[Code]
```cpp line-numbers
#include<bits/stdc++.h>
#define int long long
const int N=5e4+10;
using namespace std;
int n,ans;
int c[N];
int F[N];
int cnt,p[N];
bool vis[N];
inline int read(){
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
return ret*f;
}
void _init(){
F[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i]){
p[++cnt]=i;
F[i]=-i+1;
}
for(int j=1;j<=cnt&&i*p[j]<=n;j++){
vis[i*p[j]]=1;
if(i%p[j]){
F[i*p[j]]=F[i]*(-p[j]+1);
}else{
F[i*p[j]]=F[i];
break;
}
}
}
}
int G(int x){
int ret=0;
for(int i=1;i<=n/x;i++)ret+=i*c[x*i];
return ret;
}
signed main(){
int _n=read();
while(_n--){
int x=read();
n=max(n,x);
c[x]++;
}
_init();
for(int i=1;i<=n;i++){
int tmp=G(i);
ans+=i*F[i]*tmp*tmp;
}
printf("%lld\n",ans);
return 0;
}
```
:::
## P10636 BZOJ3518 点组计数
>[点组计数](https://www.luogu.com.cn/problem/P10636)
>
>$\small\textbf{\textsf{\textcolor{9C3DCF}{省选/NOI−}}}
给定 n,m ，求 n \times m 的点阵中三点共线的无序三元组个数，答案对 10^9 + 7 取模。
推导过程中忽略取模。
首先同行同列的三元组个数为 \displaystyle{n \binom{m}{3} + m \binom{n}{3}} 。
考虑斜率为正的情形。枚举两个端点的横纵坐标之差 i,j ，选取端点的方案数为 (n - i)(m - j) ，选取中间点的方案数为 \gcd(i,j) - 1 。由对称性，斜率为负时贡献相同，因此最终将斜率为正的贡献乘以 2 即可。
故有：
\mathrm{Ans} = n \binom{m}{3} + m \binom{n}{3} + 2 \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} (n - i)(m - j)\left( \gcd(i,j) - 1 \right).
其中：
& \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} (n - i)(m - j)\left( \gcd(i,j) - 1 \right)\\
=& \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} (n - i)(m - j) \gcd(i,j) - \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} (n - i)(m - j)\\
=& \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} (n - i)(m - j) \gcd(i,j) - \frac{n (n - 1)}{2} \cdot \frac{m (m - 1)}{2}.
\end{aligned}
考虑 \displaystyle{\sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} (n - i)(m - j) \gcd(i,j)} ，设其为 F(n,m) 。将问题归约至 n \le m ，有：
F(n,m) &= \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} (n - i)(m - j) \gcd(i,j)\\
&= \sum\limits_{k = 1}^{n} k \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} [\gcd(i,j) = k] (n - i)(m - j)\\
&= \sum\limits_{k = 1}^{n} k \sum\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} [\gcd(p,q) = 1] (n - kp)(m - kq)\\
&= \sum\limits_{k = 1}^{n} k \sum\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} (n - kp)(m - kq) \sum\limits_{\substack{d \mid p \\ d \mid q}} \mu(d)\\
&= \sum\limits_{k = 1}^{n} k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \mu(d) \sum\limits_{\substack{p = 1 \\ d \mid p}}^{\left\lfloor \frac{n}{k} \right\rfloor} (n - kp) \sum\limits_{\substack{q = 1 \\ d \mid q}}^{\left\lfloor \frac{m}{k} \right\rfloor} (m - kq)\\
&= \sum\limits_{k = 1}^{n} k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \mu(d) \sum\limits_{u = 1}^{\left\lfloor \frac{n}{kd} \right\rfloor} (n - kdu) \sum\limits_{v = 1}^{\left\lfloor \frac{m}{kd} \right\rfloor} (m - kdv)\\
&= \sum\limits_{k = 1}^{n} k \sum\limits_{\substack{t = 1 \\ k \mid t}}^{n} \mu\left( \frac{t}{k} \right) \sum\limits_{u = 1}^{\left\lfloor \frac{n}{t} \right\rfloor} (n - tu) \sum\limits_{v = 1}^{\left\lfloor \frac{m}{t} \right\rfloor} (m - tv).
\end{aligned}
令 G(n,x) = \displaystyle{\sum\limits_{i = 1}^{\left\lfloor \frac{n}{x} \right\rfloor} (n - xi) = n \left\lfloor \frac{n}{x} \right\rfloor - \frac{x \left\lfloor \frac{n}{x} \right\rfloor \left( \left\lfloor \frac{n}{x} \right\rfloor + 1 \right)}{2}} ：
F(n,m) &= \sum\limits_{k = 1}^{n} k \sum\limits_{\substack{t = 1 \\ k \mid t}}^{n} \mu\left( \frac{t}{k} \right) G(n,t) G(m,t)\\
&= \sum\limits_{t = 1}^{n} \sum\limits_{k \mid t} k \cdot \mu\left( \frac{t}{k} \right) G(n,t) G(m,t)\\
&= \sum\limits_{t = 1}^{n} \varphi(t) G(n,t) G(m,t).
\end{aligned}
线性筛出 \varphi 即可。
视 n,m 同阶，则时间复杂度为 \mathcal{O}(n) 。
:::info[Code]
#include<bits/stdc++.h>
#define int long long
const int N=5e4+10;
const int TT=1e9+7;
using namespace std;
int n,m,ans;
int phi[N];
int cnt,p[N];
bool vis[N];
int fac[N],inv[N];
inline int read(){
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
return ret*f;
}
int qpow(int x,int y){
x%=TT;
int ret=1;
while(y){
if(y&1)ret=ret*x%TT;
x=x*x%TT;
y>>=1;
}
return ret;
}
void _init(){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i]){
p[++cnt]=i;
phi[i]=i-1;
}
for(int j=1;j<=cnt&&i*p[j]<=n;j++){
vis[i*p[j]]=1;
if(i%p[j]){
phi[i*p[j]]=phi[i]*(p[j]-1);
}else{
phi[i*p[j]]=phi[i]*p[j];
break;
}
}
}
fac[0]=inv[0]=1;
for(int i=1;i<=m;i++)fac[i]=fac[i-1]*i%TT;
inv[m]=qpow(fac[m],TT-2);
for(int i=m-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%TT;
}
int C(int x,int y){
if(x<y)return 0;
return fac[x]*inv[y]%TT*inv[x-y]%TT;
}
int G(int n,int x){
int _n=n/x;
return ((n*_n%TT-x*_n%TT*(_n+1)%TT*qpow(2,TT-2)%TT)%TT+TT)%TT;
}
int F(int n,int m){
int ret=0;
for(int i=1;i<=n;i++)ret+=phi[i]*G(n,i)%TT*G(m,i)%TT,ret%=TT;
return ret;
}
signed main(){
n=read(),m=read();
if(n>m)swap(n,m);
_init();
ans+=(n*C(m,3)%TT+m*C(n,3)%TT)%TT,ans%=TT;
ans+=F(n,m)*2%TT,ans%=TT;
ans-=n*(n-1)%TT*m%TT*(m-1)%TT*qpow(2,TT-2)%TT,ans=(ans+TT)%TT;
printf("%lld\n",ans);
return 0;
}:::
P5221 Product
Product
\small\textbf{\textsf{\textcolor{9C3DCF}{省选/NOI−}}}
给定 n ，求：
\left( \prod\limits_{i = 1}^{n} \prod\limits_{j = 1}^{n} \frac{\operatorname{lcm}(i,j)}{\gcd(i,j)} \right) \bmod 104857601.
推导过程中忽略取模。
:::info[法一]{open}
首先有：
\mathrm{Ans} = \prod\limits_{i = 1}^{n} \prod\limits_{j = 1}^{n} \frac{ij}{\left( \gcd(i,j) \right)^2}.
设：
F(n) = \prod\limits_{i = 1}^{n} \prod\limits_{j = 1}^{n} \gcd(i,j).
则：
\mathrm{Ans} = \frac{(n !)^{2n}}{\left( F(n) \right)^2}.
考虑 F(n) ：
F(n) &= \prod\limits_{k = 1}^{n} \prod\limits_{i = 1}^{n} \prod\limits_{j = 1}^{n} k \uparrow [\gcd(i,j) = k]\\
&= \prod\limits_{k = 1}^{n} \prod\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right \rfloor} \prod\limits_{q = 1}^{\left\lfloor \frac{n}{k} \right \rfloor} k \uparrow [\gcd(p,q) = 1]\\
&= \prod\limits_{k = 1}^{n} \prod\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right \rfloor} \prod\limits_{q = 1}^{\left\lfloor \frac{n}{k} \right \rfloor} k \uparrow \left( \sum\limits_{d \mid \gcd(p,q)} \mu(d) \right)\\
&= \prod\limits_{k = 1}^{n} \prod\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right \rfloor} \prod\limits_{q = 1}^{\left\lfloor \frac{n}{k} \right \rfloor} \prod\limits_{d \mid \gcd(p,q)} k \uparrow \mu(d)\\
&= \prod\limits_{k = 1}^{n} \prod\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right \rfloor} \prod\limits_{q = 1}^{\left\lfloor \frac{n}{k} \right \rfloor} \prod\limits_{\substack{d \mid p \\ d \mid q}} k \uparrow \mu(d)\\
&= \prod\limits_{k = 1}^{n} \prod\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right \rfloor} \prod\limits_{\substack{p = 1 \\ d \mid p}}^{\left\lfloor \frac{n}{k} \right \rfloor} \prod\limits_{\substack{q = 1 \\ d \mid q}}^{\left\lfloor \frac{n}{k} \right \rfloor} k \uparrow \mu(d)\\
&= \prod\limits_{k = 1}^{n} \prod\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right \rfloor} \prod\limits_{u = 1}^{\left\lfloor \frac{n}{kd} \right \rfloor} \prod\limits_{v = 1}^{\left\lfloor \frac{n}{kd} \right \rfloor} k \uparrow \mu(d)\\
&= \prod\limits_{k = 1}^{n} \prod\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right \rfloor} k \uparrow \left( \mu(d) \left\lfloor \frac{n}{kd} \right\rfloor ^2 \right)\\
&= \prod\limits_{k = 1}^{n} \prod\limits_{\substack{t = 1 \\ k \mid t}}^{n} k \uparrow \left( \mu \left( \frac{t}{k} \right) \left\lfloor \frac{n}{t} \right\rfloor ^2 \right)\\
&= \prod\limits_{t = 1}^{n} \prod\limits_{k \mid t} k \uparrow \left( \mu \left( \frac{t}{k} \right) \left\lfloor \frac{n}{t} \right\rfloor ^2 \right)\\
&= \prod\limits_{t = 1}^{n} \left( \prod\limits_{k \mid t} k \uparrow \mu \left( \frac{t}{k} \right) \right) \uparrow \left( \left\lfloor \frac{n}{t} \right\rfloor ^2 \right).
\end{aligned}
其中 a \uparrow b = a^b 为 Knuth 箭头。
令 G(n) = \displaystyle{\prod\limits_{k \mid n} k \uparrow \mu \left( \frac{n}{k} \right)} ：
F(n) = \prod\limits_{t = 1}^{n} G(t) \uparrow \left( \left\lfloor \frac{n}{t} \right\rfloor ^2 \right).
考虑 G(n) 。两边取对数，得：
\ln G(n) = \sum\limits_{k \mid n} \ln(k) \, \mu\left( \frac{n}{k} \right).
考虑满足 \displaystyle{\ln n = \sum\limits_{d \mid n} \Lambda(d)} 的数论函数 \Lambda （von Mangoldt 函数）。
由 \ln = \Lambda * \mathbf{1} ，有 \ln * \,\mu = \Lambda ：
\ln G(n) = \Lambda(n) = \begin{cases}\ln p, & n = p^c, \, p \in \mathbb{P}, \, c \in \mathbb{N}_{+}, \\ 0, & \text{otherwise}.\end{cases}
其中 p \in \mathbb{P} ，c \in \mathbb{N}_{+} 。
于是：
G(n) = \begin{cases}p, & n = p^c, \, p \in \mathbb{P}, \, c \in \mathbb{N}_{+}, \\ 1, & \text{otherwise}.\end{cases}
:::
:::info[法二]{open}
考虑：
F(n) = \prod\limits_{i = 1}^{n} \prod\limits_{j = 1}^{n} \gcd(i,j).
两边取对数：
\ln F(n) &= \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{n} \ln \gcd(i,j)\\
&= \sum\limits_{k = 1}^{n} \ln k \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{n} [\gcd(i,j) = k]\\
&= \sum\limits_{k = 1}^{n} \ln k \sum\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} [\gcd(p,q) = 1]\\
&= \sum\limits_{k = 1}^{n} \ln k \sum\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{d \mid \gcd(p,q)} \mu(d)\\
&= \sum\limits_{k = 1}^{n} \ln k \sum\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{\substack{d \mid p \\ d \mid q}} \mu(d)\\
&= \sum\limits_{k = 1}^{n} \ln k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \mu(d) \sum\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} [d \mid p] \sum\limits_{q = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} [d \mid q]\\
&= \sum\limits_{k = 1}^{n} \ln k \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \mu(d) \left\lfloor \frac{n}{kd} \right\rfloor ^2\\
&= \sum\limits_{k = 1}^{n} \ln k \sum\limits_{\substack{t = 1 \\ k \mid t}}^{n} \mu \left( \frac{t}{k} \right) \left\lfloor \frac{n}{t} \right\rfloor ^2\\
&= \sum\limits_{t = 1}^{n} \sum\limits_{k \mid t} \ln(k) \mu \left( \frac{t}{k} \right) \left\lfloor \frac{n}{t} \right\rfloor ^2\\
&= \sum\limits_{t = 1}^{n} \Lambda(t) \left\lfloor \frac{n}{t} \right\rfloor ^2.
\end{aligned}
于是：
F(n) = \prod\limits_{t = 1}^{n} G(t) \uparrow \left( \left\lfloor \frac{n}{t} \right\rfloor ^2 \right).
:::
:::info[法三]{open}
考虑：
\ln F(n) = \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{n} \ln \gcd(i,j).
由 \ln = \Lambda * \mathbf{1} ：
\ln F(n) &= \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{n} \sum\limits_{d \mid \gcd(i,j)} \Lambda(d)\\
&= \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{n} \sum\limits_{\substack{d \mid i \\ d \mid j}} \Lambda(d)\\
&= \sum\limits_{d = 1}^{n} \Lambda(d) \sum\limits_{i = 1}^{n} [d \mid i] \sum\limits_{j = 1}^{n} [d \mid j]\\
&= \sum\limits_{d = 1}^{n} \Lambda(d) \left\lfloor \frac{n}{d} \right\rfloor ^2.
\end{aligned}
:::
预处理出 G 的前缀积后数论分块即可。注意指数应对 104857600 取模。
时间复杂度：预处理 \mathcal{O}(n) ，数论分块 \mathcal{O}(\sqrt{n} \log n) ，总复杂度 \mathcal{O}(n) 。如果是多组数据的话可以做到 \mathcal{O}(n + T \sqrt{n} \log n) 。
:::info[Code]
#include<bits/stdc++.h>
#define int long long
const int N=1e6+10;
const int TT=104857601;
using namespace std;
int n,ans;
int cnt,p[N];
bool vis[N];
int G[N];
inline int read(){
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
return ret*f;
}
int qpow(int x,int y){
x%=TT;
int ret=1;
while(y){
if(y&1)ret=ret*x%TT;
x=x*x%TT;
y>>=1;
}
return ret;
}
void _init(){
for(int i=2;i<=n;i++){
if(!vis[i])p[++cnt]=i;
for(int j=1;j<=cnt&&i*p[j]<=n;j++){
vis[i*p[j]]=1;
if(!(i%p[j]))break;
}
}
for(int i=0;i<=n;i++)G[i]=1;
for(int i=1;i<=cnt;i++)for(int j=p[i];j<=n;j*=p[i])G[j]=p[i];
for(int i=1;i<=n;i++)G[i]=G[i]*G[i-1]%TT;
}
int F(int n){
int ret=1;
for(int l=1,r;l<=n;l=r+1){
r=n/(n/l);
int tmp=G[r]*qpow(G[l-1],TT-2)%TT;
ret=ret*qpow(tmp,(n/l)*(n/l)%(TT-1))%TT;
}
return ret;
}
signed main(){
n=read();
_init();
int fac=1;
for(int i=1;i<=n;i++)fac=fac*i%TT;
ans=qpow(fac,n*2);
int tmp=F(n);
ans=ans*qpow(tmp*tmp%TT,TT-2)%TT;
printf("%lld\n",ans);
return 0;
}:::
P3327 [SDOI2015] 约数个数和
约数个数和
\small\textbf{\textsf{\textcolor{9C3DCF}{省选/NOI−}}}
给定 n,m ，求：
\sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \sigma_0(ij).
多测，T 组数据，1 \le T,n,m \le 5 \times 10^4 。
首先有一个结论：
\sigma_0(ij) = \sum\limits_{x \mid i} \sum\limits_{y \mid j} [\gcd(x,y) = 1].
:::info[证明]{open}
考虑等式左边。设：
i = \prod\limits_{p} p^{a_p}, \ j = \prod\limits_{p} p^{b_p}.
其中 p \in \mathbb{P} ，下同。
则：
ij = \prod\limits_{p} p^{a_p + b_p}.
于是：
\sigma_0(ij) = \prod\limits_{p} (a_p + b_p + 1).
考虑等式右边。设：
x = \prod\limits_{p} p^{c_p}, \ y = \prod\limits_{p} p^{d_p}.
对于每个 p ，设合法的 (c_p,d_p) 对数为 f(p) ，而合法的 (x,y) 对数就等于各 f(p) 之积。故等式右边即为：
\prod\limits_{p} f(p).
考虑 c_p 与 d_p 的限制条件：
由 x \mid i ，有 c_p \le a_p 。
由 y \mid j ，有 d_p \le b_p 。
由 \gcd(x,y) = 1 ，有 c_p 与 d_p 不均为正，即 c_p d_p = 0 。
因此：
当 c_p = d_p = 0 时，方案数为 1 。
当 c_p = 0 ，d_p \in [1,b_p] 时，方案数为 b_p 。
当 d_p = 0 ，c_p \in [1,a_p] 时，方案数为 a_p 。
故：
f(p) = a_p + b_p + 1.
因此等式右边即为：
\prod\limits_{p} (a_p + b_p + 1).
证毕。
:::
设 n \le m 。
:::info[法一]{open}
利用上面的结论推式子：
\mathrm{Ans} &= \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \sum\limits_{x \mid i} \sum\limits_{y \mid j} [\gcd(x,y) = 1]\\
&= \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \sum\limits_{x \mid i} \sum\limits_{y \mid j} \sum\limits_{d \mid \gcd(x,y)} \mu(d)\\
&= \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \sum\limits_{x \mid i} \sum\limits_{y \mid j} \sum\limits_{\substack{d \mid x \\ d \mid y}} \mu(d)\\
&= \sum\limits_{d = 1}^{n} \mu(d) \sum\limits_{\substack{x = 1 \\ d \mid x}}^{n} \sum\limits_{\substack{i = 1 \\ x \mid i}}^{n} \sum\limits_{\substack{y = 1 \\ d \mid y}}^{m} \sum\limits_{\substack{j = 1 \\ y \mid j}}^{m} 1\\
&= \sum\limits_{d = 1}^{n} \mu(d) \sum\limits_{\substack{x = 1 \\ d \mid x}}^{n} \left\lfloor \frac{n}{x} \right\rfloor \sum\limits_{\substack{y = 1 \\ d \mid y}}^{m} \left\lfloor \frac{m}{y} \right\rfloor\\
&= \sum\limits_{d = 1}^{n} \mu(d) \sum\limits_{u = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} \left\lfloor \frac{n}{ud} \right\rfloor \sum\limits_{v = 1}^{\left\lfloor \frac{m}{d} \right\rfloor} \left\lfloor \frac{m}{vd} \right\rfloor\\
&= \sum\limits_{d = 1}^{n} \mu(d) \sum\limits_{u = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} \left\lfloor \frac{\left\lfloor \frac{n}{d} \right\rfloor}{u} \right\rfloor \sum\limits_{v = 1}^{\left\lfloor \frac{m}{d} \right\rfloor} \left\lfloor \frac{\left\lfloor \frac{m}{d} \right\rfloor}{v} \right\rfloor.
\end{aligned}
设 S_0(n) = \displaystyle{\sum\limits_{i = 1}^{n} \left\lfloor \frac{n}{i} \right\rfloor} = \sum\limits_{i = 1}^{n} \sigma_0(i) ：
\mathrm{Ans} = \sum\limits_{d = 1}^{n} \mu(d) S_0 \left( \left\lfloor \frac{n}{d} \right\rfloor \right) S_0 \left( \left\lfloor \frac{m}{d} \right\rfloor \right).
:::
:::info[法二]{open}
先对关键结论进行变形：
\sigma_0(ij) &= \sum\limits_{x \mid i} \sum\limits_{y \mid j} [\gcd(x,y) = 1]\\
&= \sum\limits_{x \mid i} \sum\limits_{y \mid j} \sum\limits_{d \mid \gcd(x,y)} \mu(d)\\
&= \sum\limits_{x \mid i} \sum\limits_{y \mid j} \sum\limits_{\substack{d \mid x \\ d \mid y}} \mu(d)\\
&= \sum\limits_{\substack{d \mid i \\ d \mid j}} \mu(d) \sum\limits_{\substack{x \mid i \\ d \mid x}} \sum\limits_{\substack{y \mid j \\ d \mid y}} 1\\
&= \sum\limits_{\substack{d \mid i \\ d \mid j}} \mu(d) \sum\limits_{pd \mid i} \sum\limits_{qd \mid j} 1\\
&= \sum\limits_{\substack{d \mid i \\ d \mid j}} \mu(d) \sum\limits_{p \mid \frac{i}{d}} \sum\limits_{q \mid \frac{j}{d}} 1\\
&= \sum\limits_{\substack{d \mid i \\ d \mid j}} \mu(d) \sigma_0 \left( \frac{i}{d} \right) \sigma_0 \left( \frac{j}{d} \right).
\end{aligned}
代入：
\mathrm{Ans} &= \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \sum\limits_{\substack{d \mid i \\ d \mid j}} \mu(d) \sigma_0 \left( \frac{i}{d} \right) \sigma_0 \left( \frac{j}{d} \right)\\
&= \sum\limits_{d = 1}^{n} \mu(d) \sum\limits_{\substack{i = 1 \\ d \mid i}}^{n} \sigma_0 \left( \frac{i}{d} \right) \sum\limits_{\substack{j = 1 \\ d \mid j}}^{m} \sigma_0 \left( \frac{j}{d} \right)\\
&= \sum\limits_{d = 1}^{n} \mu(d) \sum\limits_{p = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} \sigma_0(p) \sum\limits_{q = 1}^{\left\lfloor \frac{m}{d} \right\rfloor} \sigma_0(q)\\
&= \sum\limits_{d = 1}^{n} \mu(d) S_0 \left( \left\lfloor \frac{n}{d} \right\rfloor \right) S_0 \left( \left\lfloor \frac{m}{d} \right\rfloor \right).
\end{aligned}
:::
预处理出 \mu 的前缀和与 S_0 后数论分块即可。
视 n,m 同阶，则时间复杂度为 \mathcal{O}\left( n + T \sqrt{n} \right) 。
:::info[Code]
#include<bits/stdc++.h>
#define int long long
const int N=5e4+10;
using namespace std;
int T;
int _n=5e4;
int n,m,ans;
int mu[N];
int tmp[N],sig_0[N];
int cnt,p[N];
bool vis[N];
inline int read(){
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
return ret*f;
}
void _init(){
mu[1]=sig_0[1]=1;
for(int i=2;i<=_n;i++){
if(!vis[i]){
p[++cnt]=i;
mu[i]=-1;
tmp[i]=sig_0[i]=2;
}
for(int j=1;j<=cnt&&i*p[j]<=_n;j++){
vis[i*p[j]]=1;
if(i%p[j]){
mu[i*p[j]]=-mu[i];
tmp[i*p[j]]=2;
sig_0[i*p[j]]=sig_0[i]*2;
}else{
mu[i*p[j]]=0;
tmp[i*p[j]]=tmp[i]+1;
sig_0[i*p[j]]=sig_0[i]/tmp[i]*(tmp[i]+1);
break;
}
}
}
for(int i=1;i<=_n;i++)mu[i]+=mu[i-1],sig_0[i]+=sig_0[i-1];
}
void _solve(){
n=read(),m=read();
ans=0;
if(n>m)swap(n,m);
for(int l=1,r;l<=n;l=r+1){
r=min(n/(n/l),m/(m/l));
ans+=(mu[r]-mu[l-1])*sig_0[n/l]*sig_0[m/l];
}
printf("%lld\n",ans);
}
signed main(){
_init();
T=read();
while(T--)_solve();
return 0;
}:::
P4240 毒瘤之神的考验
毒瘤之神的考验
\small\textbf{\textsf{\textcolor{0E1D69}{NOI/NOI+/CTS}}}
给定 n,m ，求：
\left( \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \varphi(ij) \right) \bmod 998244353.
多测，T 组数据，1 \le T \le 10^4 ，1 \le n,m \le 10^5 。
首先有一个结论：
\varphi(ij) = \frac{\varphi(i) \varphi(j) \gcd(i,j)}{\varphi(\gcd(i,j))}.
:::info[证明]{open}
我们要证明的等式是：
\varphi(ij) \varphi(\gcd(i,j)) = \varphi(i) \varphi(j) \gcd(i,j).
左边为：
& \left( ij \prod\limits_{p \mid ij} \left( 1 - \frac{1}{p} \right) \right) \left( \gcd(i,j) \prod\limits_{p \mid \gcd(i,j)} \left( 1 - \frac{1}{p} \right) \right)\\
=& \left( ij \prod\limits_{p \mid i \ \lor \ p \mid j} \left( 1 - \frac{1}{p} \right) \right) \left( \gcd(i,j) \prod\limits_{p \mid i \ \land \ p \mid j} \left( 1 - \frac{1}{p} \right) \right)\\
=& \ ij \gcd(i,j) \left( \prod\limits_{p \mid i \ \lor \ p \mid j} \left( 1 - \frac{1}{p} \right) \right) \left( \prod\limits_{p \mid i \ \land \ p \mid j} \left( 1 - \frac{1}{p} \right) \right).
\end{aligned}
其中 p \in \mathbb{P} ，下同。
右边为：
& \left( i \prod\limits_{p \mid i} \left( 1 - \frac{1}{p} \right) \right) \left( j \prod\limits_{p \mid j} \left( 1 - \frac{1}{p} \right) \right) \gcd(i,j)\\
=& \ ij \gcd(i,j) \left( \prod\limits_{p \mid i} \left( 1 - \frac{1}{p} \right) \right) \left( \prod\limits_{p \mid j} \left( 1 - \frac{1}{p} \right) \right).
\end{aligned}
由容斥原理，两者相等。证毕。
:::
设 n \le m 。推导中忽略取模。
复杂度分析中视 n,m 同阶。
利用上面的结论推式子：
\mathrm{Ans} &= \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \frac{\varphi(i) \varphi(j) \gcd(i,j)}{\varphi(\gcd(i,j))}\\
&= \sum\limits_{k = 1}^{n} \frac{k}{\varphi(k)} \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} [\gcd(i,j) = k] \varphi(i) \varphi(j)\\
&= \sum\limits_{k = 1}^{n} \frac{k}{\varphi(k)} \sum\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} [\gcd(p,q) = 1] \varphi(kp) \varphi(kq)\\
&= \sum\limits_{k = 1}^{n} \frac{k}{\varphi(k)} \sum\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} \varphi(kp) \varphi(kq) \sum\limits_{d \mid \gcd(p,q)} \mu(d)\\
&= \sum\limits_{k = 1}^{n} \frac{k}{\varphi(k)} \sum\limits_{p = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} \varphi(kp) \varphi(kq) \sum\limits_{\substack{d \mid p \\ d \mid q}} \mu(d)\\
&= \sum\limits_{k = 1}^{n} \frac{k}{\varphi(k)} \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \mu(d) \sum\limits_{\substack{p = 1 \\ d \mid p}}^{\left\lfloor \frac{n}{k} \right\rfloor} \varphi(kp) \sum\limits_{\substack{q = 1 \\ d \mid q}}^{\left\lfloor \frac{m}{k} \right\rfloor} \varphi(kq)\\
&= \sum\limits_{k = 1}^{n} \frac{k}{\varphi(k)} \sum\limits_{d = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \mu(d) \sum\limits_{u = 1}^{\left\lfloor \frac{n}{kd} \right\rfloor} \varphi(kdu) \sum\limits_{v = 1}^{\left\lfloor \frac{m}{kd} \right\rfloor} \varphi(kdv)\\
&= \sum\limits_{k = 1}^{n} \frac{k}{\varphi(k)} \sum\limits_{\substack{t = 1 \\ k \mid t}}^{n} \mu \left( \frac{t}{k} \right) \sum\limits_{u = 1}^{\left\lfloor \frac{n}{t} \right\rfloor} \varphi(tu) \sum\limits_{v = 1}^{\left\lfloor \frac{m}{t} \right\rfloor} \varphi(tv).
\end{aligned}
令 G(x,y) = \displaystyle{\sum\limits_{i = 1}^{y} \varphi(xi)} ：
\mathrm{Ans} &= \sum\limits_{k = 1}^{n} \frac{k}{\varphi(k)} \sum\limits_{\substack{t = 1 \\ k \mid t}}^{n} \mu \left( \frac{t}{k} \right) G \left( t, \left\lfloor \frac{n}{t} \right\rfloor \right) G \left( t, \left\lfloor \frac{m}{t} \right\rfloor \right)\\
&= \sum\limits_{t = 1}^{n} \sum\limits_{k \mid t} \frac{k}{\varphi(k)} \cdot \mu \left( \frac{t}{k} \right) G \left( t, \left\lfloor \frac{n}{t} \right\rfloor \right) G \left( t, \left\lfloor \frac{m}{t} \right\rfloor \right).
\end{aligned}
令 F(x) = \displaystyle{ \sum\limits_{k \mid x} \frac{k}{\varphi(k)} \cdot \mu \left( \frac{x}{k} \right)} ：
\mathrm{Ans} = \sum\limits_{t = 1}^{n} F(t) G \left( t, \left\lfloor \frac{n}{t} \right\rfloor \right) G \left( t, \left\lfloor \frac{m}{t} \right\rfloor \right).
首先预处理出 i \in [1,m] 的 \varphi(i) 与 \dfrac{i}{\varphi(i)} ，复杂度 \mathcal{O(n \log n)} 。
对于 F(x) ，用 Dirichlet 差分预处理。复杂度 \mathcal{O}(n \log \log n) 。
对于 G(x,y) ，有递推式：
G(x,y) = G(x, y - 1) + \varphi(xy).
显然有 xy \le m 。于是预处理 G(x,y) 的复杂度为 \mathcal{O(n \log n)} 。
考虑数论分块。
设：
H(a,b,c) = \sum\limits_{i = 1}^{c} F(i) G(i, a) G(i, b).
则在数论分块中，块 [l,r] 的贡献可表示为：
H \left( \left\lfloor \frac{n}{r} \right\rfloor , \left\lfloor \frac{m}{r} \right\rfloor , r \right) - H \left( \left\lfloor \frac{n}{r} \right\rfloor , \left\lfloor \frac{m}{r} \right\rfloor , l - 1 \right).
考虑预处理出一部分 H(a,b,c) 。
设置一个预处理阈值 B 。
显然有 ac \le n 与 bc \le m 。
对于所有 a \in [1, B], b \in [1, B] ，预处理出 H(a,b,1) \sim H \left( a,b, \min \left( \left\lfloor \dfrac{n}{a} \right\rfloor , \left\lfloor \dfrac{m}{b} \right\rfloor \right) \right) 。
递推式：
H(a,b,c) = H(a, b, c - 1) + F(c) G(c,a) G(c,b).
预处理 H(a,b,c) 的复杂度为：
& \, \mathcal{O} \left( \sum\limits_{i = 1}^{B} \sum\limits_{j = 1}^{B} \min \left( \frac{n}{i} , \frac{n}{j} \right) \right)\\
=& \, \mathcal{O} \left( \sum\limits_{i = 1}^{B} \sum\limits_{j = 1}^{i} \frac{n}{i} \right)\\
=& \, \mathcal{O} \left( \sum\limits_{i = 1}^{B} i \cdot \frac{n}{i} \right)\\
=& \, \mathcal{O} \left( nB \right).\\
\end{aligned}
数论分块中，对于一个块 [l,r] ，若 \left\lfloor \dfrac{m}{r} \right\rfloor > B ，则暴力计算这一块的贡献。
可以证明此时 r \le \left\lfloor \dfrac{m}{B + 1} \right\rfloor ，故计算所有 \left\lfloor \dfrac{m}{r} \right\rfloor > B 的块的复杂度为 \mathcal{O} \left( \dfrac{n}{B} \right) 。
若 \left\lfloor \dfrac{m}{r} \right\rfloor \le B ，借助预处理好的 H 函数可直接得到该块贡献。
总复杂度为 \mathcal{O} \left( n \log n + nB + T \left( \sqrt{n} + \dfrac{n}{B} \right) \right) 。
当 B = \Theta(\sqrt{T}) 时，复杂度为 \mathcal{O} \left( n \log n + n \sqrt{T} + T \sqrt{n} \right) 。
:::info[Code]
#include<bits/stdc++.h>
#define int long long
#define vi vector<int>
const int N=1e5+10;
const int B=110;
const int TT=998244353;
using namespace std;
int T;
int _n=1e5;
int b;
int n,m,ans;
int phi[N];
int cnt,p[N];
bool vis[N];
int F[N];
vi G[N];
vi H[B][B];
inline int read(){
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
return ret*f;
}
int qpow(int x,int y){
x%=TT;
int ret=1;
while(y){
if(y&1)ret=ret*x%TT;
x=x*x%TT;
y>>=1;
}
return ret;
}
void _init(){
phi[1]=1;
for(int i=2;i<=_n;i++){
if(!vis[i]){
p[++cnt]=i;
phi[i]=i-1;
}
for(int j=1;j<=cnt&&i*p[j]<=_n;j++){
vis[i*p[j]]=1;
if(i%p[j]){
phi[i*p[j]]=phi[i]*(p[j]-1)%TT;
}else{
phi[i*p[j]]=phi[i]*p[j]%TT;
break;
}
}
}
for(int i=1;i<=_n;i++)F[i]=i*qpow(phi[i],TT-2)%TT;
for(int i=1;i<=cnt;i++)for(int j=_n/p[i];j>=1;j--)F[p[i]*j]=(F[p[i]*j]-F[j]+TT)%TT;
for(int i=1;i<=_n;i++){
G[i].resize(_n/i+10);
for(int j=1;j<=_n/i;j++)G[i][j]=(G[i][j-1]+phi[i*j])%TT;
}
b=(int)sqrt(T);
for(int i=1;i<=b;i++){
for(int j=1;j<=b;j++){
int siz=min(_n/i,_n/j);
H[i][j].resize(siz+10);
for(int k=1;k<=siz;k++)H[i][j][k]=(H[i][j][k-1]+F[k]*G[k][i]%TT*G[k][j]%TT)%TT;
}
}
}
void _solve(){
n=read(),m=read();
ans=0;
if(n>m)swap(n,m);
for(int l=1,r;l<=n;l=r+1){
r=min(n/(n/l),m/(m/l));
if(m/r>b)for(int i=l;i<=r;i++)ans=(ans+F[i]*G[i][n/i]%TT*G[i][m/i]%TT)%TT;
else ans=(ans+H[n/r][m/r][r]-H[n/r][m/r][l-1]+TT)%TT;
}
printf("%lld\n",ans);
}
signed main(){
T=read();
_init();
while(T--)_solve();
return 0;
}:::
P13645 Totient with Divisors
Totient with Divisors
\small\textbf{\textsf{\textcolor{0E1D69}{NOI/NOI+/CTS}}}
给定 n,m ，求：
\left( \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \varphi(i) \varphi(j) \sigma_1(ij) \right) \bmod 998244353.
多测，T 组数据，1 \le T,n,m \le 10^5 。
首先有一个结论：
\sigma_1(ij) = \sum\limits_{x \mid i} \sum\limits_{y \mid j} \frac{yi}{x} [\gcd(x,y) = 1].
:::info[证明]{open}
考虑等式左边。设：
i = \prod\limits_{p} p^{a_p}, \ j = \prod\limits_{p} p^{b_p}.
其中 p \in \mathbb{P} ，下同。
则：
ij = \prod\limits_{p} p^{a_p + b_p}.
于是：
\sigma_1(ij) = \prod\limits_{p} \left( \sum\limits_{k = 0}^{a_p + b_p} p^k \right).
考虑等式右边。设：
x = \prod\limits_{p} p^{c_p}, \ y = \prod\limits_{p} p^{d_p}.
则：
\frac{yi}{x} = \prod\limits_{p} p^{a_p -c_p + d_p}.
考虑 c_p 与 d_p 的限制条件：
由 x \mid i ，有 c_p \le a_p 。
由 y \mid j ，有 d_p \le b_p 。
由 \gcd(x,y) = 1 ，有 c_p d_p = 0 。
因此等式右边为：
& \prod\limits_{p} \left( \sum\limits_{c_p = 0}^{a_p} \sum\limits_{d_p = 0}^{b_p} [c_p d_p = 0] p^{a_p - c_p + d_p} \right)\\
=& \prod\limits_{p} \left( p^{a_p} + \sum\limits_{c_p = 1}^{a_p} p^{a_p - c_p} + \sum\limits_{d_p = 1}^{b_p} p^{a_p + d_p} \right)\\
=& \prod\limits_{p} \left( p^{a_p} + \sum\limits_{k = 1}^{a_p - 1} p^k + \sum\limits_{k = a_p + 1}^{a_p + b_p} p^k \right)\\
=& \prod\limits_{p} \left( \sum\limits_{k = 0}^{a_p + b_p} p^k \right).
\end{aligned}
证毕。
:::
设 n \le m 。推导中忽略取模。
复杂度分析中视 n,m 同阶。
:::info[法一]{open}
利用上面的结论推式子：
\mathrm{Ans} &= \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \varphi(i) \varphi(j) \sum\limits_{x \mid i} \sum\limits_{y \mid j} \frac{yi}{x} [\gcd(x,y) = 1]\\
&= \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \varphi(i) \varphi(j) \sum\limits_{x \mid i} \sum\limits_{y \mid j} \frac{yi}{x} \sum\limits_{d \mid \gcd(x,y)} \mu(d)\\
&= \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \varphi(i) \varphi(j) \sum\limits_{x \mid i} \sum\limits_{y \mid j} \frac{yi}{x} \sum\limits_{\substack{d \mid x \\ d \mid y}} \mu(d)\\
&= \sum\limits_{d = 1}^{n} \mu(d) \sum\limits_{\substack{x = 1 \\ d \mid x}}^{n} \sum\limits_{\substack{i = 1 \\ x \mid i}}^{n} \frac{i}{x} \cdot \varphi(i) \sum\limits_{\substack{y = 1 \\ d \mid y}}^{m} \sum\limits_{\substack{j = 1 \\ y \mid j}}^{m} y \cdot \varphi(j)\\
&= \sum\limits_{d = 1}^{n} \mu(d) \sum\limits_{\substack{x = 1 \\ d \mid x}}^{n} \sum\limits_{p = 1}^{\left\lfloor \frac{n}{x} \right\rfloor} p \cdot \varphi(px) \sum\limits_{\substack{y = 1 \\ d \mid y}}^{m} \sum\limits_{q = 1}^{\left\lfloor \frac{m}{y} \right\rfloor} y \cdot \varphi(qy)\\
&= \sum\limits_{d = 1}^{n} \mu(d) \sum\limits_{u = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} \sum\limits_{p = 1}^{\left\lfloor \frac{n}{du} \right\rfloor} p \cdot \varphi(pud) \sum\limits_{v = 1}^{\left\lfloor \frac{m}{d} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{m}{dv} \right\rfloor} vd \cdot \varphi(qvd)\\
&= \sum\limits_{d = 1}^{n} d \cdot \mu(d) \sum\limits_{u = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} \sum\limits_{p = 1}^{\left\lfloor \frac{n}{du} \right\rfloor} p \cdot \varphi(pud) \sum\limits_{v = 1}^{\left\lfloor \frac{m}{d} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{m}{dv} \right\rfloor} v \cdot \varphi(qvd).
\end{aligned}
其中：
& \sum\limits_{u = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} \sum\limits_{p = 1}^{\left\lfloor \frac{n}{du} \right\rfloor} p \cdot \varphi(pud)\\
=& \sum\limits_{u = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} \sum\limits_{\substack{k = 1 \\ u \mid k}}^{\left\lfloor \frac{n}{d} \right\rfloor} \frac{k}{u} \cdot \varphi(kd)\\
=& \sum\limits_{k = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} \varphi(kd) \sum\limits_{u \mid k} \frac{k}{u}\\
=& \sum\limits_{k = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} \varphi(kd) \sigma_1(k).
\end{aligned}
同样地，有：
& \sum\limits_{v = 1}^{\left\lfloor \frac{m}{d} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{m}{dv} \right\rfloor} v \cdot \varphi(qvd)\\
=& \sum\limits_{v = 1}^{\left\lfloor \frac{m}{d} \right\rfloor} \sum\limits_{\substack{k = 1 \\ v \mid k}}^{\left\lfloor \frac{m}{d} \right\rfloor} v \cdot \varphi(kd)\\
=& \sum\limits_{k = 1}^{\left\lfloor \frac{m}{d} \right\rfloor} \varphi(kd) \sum\limits_{v \mid k} v\\
=& \sum\limits_{k = 1}^{\left\lfloor \frac{m}{d} \right\rfloor} \varphi(kd) \sigma_1(k).
\end{aligned}
令 F(x) = x \cdot \mu(x) ，G(x,y) = \displaystyle{\sum\limits_{i = 1}^{y}} \varphi(xi) \sigma_1(i) ：
\mathrm{Ans} = \sum\limits_{d = 1}^{n} F(d) G \left( d, \left\lfloor \frac{n}{d} \right\rfloor \right) G \left( d, \left\lfloor \frac{m}{d} \right\rfloor \right).
:::
:::info[法二]{open}
先对关键结论进行变形：
\sigma_1(ij) &= \sum\limits_{x \mid i} \sum\limits_{y \mid j} \frac{yi}{x} [\gcd(x,y) = 1]\\
&= \sum\limits_{x \mid i} \sum\limits_{y \mid j} \frac{yi}{x} \sum\limits_{d \mid \gcd(x,y)} \mu(d)\\
&= \sum\limits_{x \mid i} \sum\limits_{y \mid j} \frac{yi}{x} \sum\limits_{\substack{d \mid x \\ d \mid y}} \mu(d)\\
&= \sum\limits_{\substack{d \mid i \\ d \mid j}} \mu(d) \sum\limits_{\substack{x \mid i \\ d \mid x}} \frac{i}{x} \sum\limits_{\substack{y \mid j \\ d \mid y}} y\\
&= \sum\limits_{\substack{d \mid i \\ d \mid j}} \mu(d) \sum\limits_{pd \mid i} \frac{i}{pd} \sum\limits_{qd \mid j} qd\\
&= \sum\limits_{\substack{d \mid i \\ d \mid j}} d \cdot \mu(d) \sum\limits_{pd \mid i} \frac{i}{pd} \sum\limits_{qd \mid j} q\\
&= \sum\limits_{\substack{d \mid i \\ d \mid j}} d \cdot \mu(d) \sum\limits_{p \mid \frac{i}{d}} \frac{\,\frac{i}{d}\,}{p} \sum\limits_{q \mid \frac{j}{d}} q\\
&= \sum\limits_{\substack{d \mid i \\ d \mid j}} d \cdot \mu(d) \sigma_1 \left( \frac{i}{d} \right) \sigma_1 \left( \frac{j}{d} \right).
\end{aligned}
代入：
\mathrm{Ans} &= \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \varphi(i) \varphi(j) \sum\limits_{\substack{d \mid i \\ d \mid j}} d \cdot \mu(d) \sigma_1 \left( \frac{i}{d} \right) \sigma_1 \left( \frac{j}{d} \right)\\
&= \sum\limits_{d = 1}^{n} d \cdot \mu(d) \sum\limits_{\substack{i = 1 \\ d \mid i}}^{n} \varphi(i) \sigma_1 \left( \frac{i}{d} \right) \sum\limits_{\substack{j = 1 \\ d \mid j}}^{m} \varphi(j) \sigma_1 \left( \frac{j}{d} \right)\\
&= \sum\limits_{d = 1}^{n} d \cdot \mu(d) \sum\limits_{p = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} \varphi(dp) \sigma_1(p) \sum\limits_{q = 1}^{\left\lfloor \frac{m}{d} \right\rfloor} \varphi(dq) \sigma_1(q)\\
&= \sum\limits_{d = 1}^{n} F(d) G \left( d, \left\lfloor \frac{n}{d} \right\rfloor \right) G \left( d, \left\lfloor \frac{m}{d} \right\rfloor \right).
\end{aligned}
:::
$$G(x,y) = G(x, y - 1) + \varphi(xy) \sigma_1(y).$$
最终式子的结构与 P4240 一致。按 P4240 的做法做即可。
时间复杂度为 $\mathcal{O}(n \log n + n \sqrt{T} + T \sqrt{n})$。
:::info[Code]
```cpp line-numbers
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
const int N=1e5+10;
const int B=326;
const int TT=998244353;
using namespace std;
int T;
int _n=1e5;
int b;
int n,m,ans;
int phi[N];
int mu[N];
int tmp[N],sig_1[N];
int cnt,p[N];
bool vis[N];
int F[N];
vi G[N];
vi H[B][B];
inline int read(){
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
return ret*f;
}
void _init(){
phi[1]=mu[1]=sig_1[1]=1;
for(int i=2;i<=_n;i++){
if(!vis[i]){
p[++cnt]=i;
phi[i]=i-1;
mu[i]=-1;
tmp[i]=sig_1[i]=i+1;
}
for(int j=1;j<=cnt&&i*p[j]<=_n;j++){
vis[i*p[j]]=1;
if(i%p[j]){
phi[i*p[j]]=phi[i]*(p[j]-1);
mu[i*p[j]]=-mu[i];
tmp[i*p[j]]=p[j]+1;
sig_1[i*p[j]]=sig_1[i]*(p[j]+1);
}else{
phi[i*p[j]]=phi[i]*p[j];
mu[i*p[j]]=0;
tmp[i*p[j]]=tmp[i]*p[j]+1;
sig_1[i*p[j]]=sig_1[i]/tmp[i]*tmp[i*p[j]];
break;
}
}
}
for(int i=1;i<=_n;i++)phi[i]%=TT,mu[i]=(TT+mu[i])%TT,sig_1[i]%=TT;
for(int i=1;i<=_n;i++)F[i]=(ll)i*mu[i]%TT;
for(int i=1;i<=_n;i++){
G[i].resize(_n/i+10);
for(int j=1;j<=_n/i;j++)G[i][j]=((ll)G[i][j-1]+(ll)phi[i*j]*sig_1[j]%TT)%TT;
}
b=(int)sqrt(T);
for(int i=1;i<=b;i++){
for(int j=1;j<=b;j++){
int siz=min(_n/i,_n/j);
H[i][j].resize(siz+10);
for(int k=1;k<=siz;k++)H[i][j][k]=((ll)H[i][j][k-1]+(ll)F[k]*G[k][i]%TT*G[k][j]%TT)%TT;
}
}
}
void _solve(){
n=read(),m=read();
ans=0;
if(n>m)swap(n,m);
for(int l=1,r;l<=n;l=r+1){
r=min(n/(n/l),m/(m/l));
if(m/r>b)for(int i=l;i<=r;i++)ans=((ll)ans+(ll)F[i]*G[i][n/i]%TT*G[i][m/i]%TT)%TT;
else ans=((ll)ans+H[n/r][m/r][r]-H[n/r][m/r][l-1]+TT)%TT;
}
printf("%d\n",ans);
}
signed main(){
T=read();
_init();
while(T--)_solve();
return 0;
}
```
:::
## P5518 [MtOI2019] 幽灵乐团 / 莫比乌斯反演基础练习题
>[幽灵乐团 / 莫比乌斯反演基础练习题](https://www.luogu.com.cn/problem/P5518)
>
>
>Formerly: $\,\small\textbf{\textsf{\textcolor{0E1D69}{NOI/NOI+/CTS}}}
Now: \,\small\textbf{\textsf{\textcolor{9C3DCF}{省选/NOI−}}}
给定 A,B,C,p ，求：
\left( \prod\limits_{i = 1}^{A} \prod\limits_{j = 1}^{B} \prod\limits_{k = 1}^{C} \left( \frac{\operatorname{lcm}(i,j)}{\gcd(i,k)} \right) ^{f(\mathrm{type})} \right) \bmod p.
其中：
\begin{cases}
f(0) = 1,\\
f(1) = ijk,\\
f(2) = \gcd(i,j,k).
\end{cases}
多测，T 组数据，T = 70 ，1 \le A,B,C \le 10^5 ，10^7 \le p \le 1.05 \times 10^9 ，p \in \mathbb{P} 。所有数据共用一个 p 。
推导过程中忽略取模。
复杂度分析中视 n 与 A,B,C 同阶。
首先有：
\mathrm{Ans}_{\mathrm{type}} &= \prod\limits_{i = 1}^{A} \prod\limits_{j = 1}^{B} \prod\limits_{k = 1}^{C} \left( \frac{ij}{\gcd(i,j) \gcd(i,k)} \right) ^{f(\mathrm{type})}\\
&= \frac{\left( \prod\limits_{i = 1}^{A} \prod\limits_{j = 1}^{B} \prod\limits_{k = 1}^{C} i^{f(\mathrm{type})} \right) \left( \prod\limits_{j = 1}^{B} \prod\limits_{i = 1}^{A} \prod\limits_{k = 1}^{C} j^{f(\mathrm{type})} \right)}{\left( \prod\limits_{i = 1}^{A} \prod\limits_{j = 1}^{B} \prod\limits_{k = 1}^{C} (\gcd(i,j))^{f(\mathrm{type})} \right) \left( \prod\limits_{i = 1}^{A} \prod\limits_{k = 1}^{C} \prod\limits_{j = 1}^{B} (\gcd(i,k))^{f(\mathrm{type})} \right)}.
\end{aligned}
令：
F_{\mathrm{type},1}(A,B,C) &= \prod\limits_{i = 1}^{A} \prod\limits_{j = 1}^{B} \prod\limits_{k = 1}^{C} i^{f(\mathrm{type})},\\
F_{\mathrm{type},2}(A,B,C) &= \prod\limits_{i = 1}^{A} \prod\limits_{j = 1}^{B} \prod\limits_{k = 1}^{C} (\gcd(i,j))^{f(\mathrm{type})}.
\end{aligned}
则：
\mathrm{Ans}_{\mathrm{type}} = \frac{F_{\mathrm{type},1}(A,B,C) \, F_{\mathrm{type},1}(B,A,C)}{F_{\mathrm{type},2}(A,B,C) \, F_{\mathrm{type},2}(A,C,B)}.
考虑 F_{0,1}(A,B,C) ：
F_{0,1}(A,B,C) = \prod\limits_{i = 1}^{A} \prod\limits_{j = 1}^{B} \prod\limits_{k = 1}^{C} i.
两边取对数：
\ln F_{0,1}(A,B,C) &= \sum\limits_{i = 1}^{A} \sum\limits_{j = 1}^{B} \sum\limits_{k = 1}^{C} \ln i\\
&= BC \sum\limits_{i = 1}^{A} \ln i.
\end{aligned}
于是：
F_{0,1}(A,B,C) &= \left( \prod\limits_{i = 1}^{A} i \right) \uparrow (BC)\\
&= (A!) \uparrow (BC).
\end{aligned}
预处理出阶乘数组后即可 \mathcal{O}(\log n) 求解。
考虑 F_{0,2}(A,B,C) ：
F_{0,2}(A,B,C) = \prod\limits_{i = 1}^{A} \prod\limits_{j = 1}^{B} \prod\limits_{k = 1}^{C} \gcd(i,j).
两边取对数：
\ln F_{0,2}(A,B,C) &= \sum\limits_{i = 1}^{A} \sum\limits_{j = 1}^{B} \sum\limits_{k = 1}^{C} \ln \gcd(i,j)\\
&= C \sum\limits_{i = 1}^{A} \sum\limits_{j = 1}^{B} \ln \gcd(i,j)\\
&= C \sum\limits_{i = 1}^{A} \sum\limits_{j = 1}^{B} \sum\limits_{d \mid \gcd(i,j)} \Lambda(d)\\
&= C \sum\limits_{i = 1}^{A} \sum\limits_{j = 1}^{B} \sum\limits_{\substack{d \mid i \\ d \mid j}} \Lambda(d)\\
&= C \sum\limits_{d = 1}^{\min(A,B)} \Lambda(d) \sum\limits_{i = 1}^{A} [d \mid i] \sum\limits_{j = 1}^{B} [d \mid j]\\
&= C \sum\limits_{d = 1}^{\min(A,B)} \Lambda(d) \left\lfloor \frac{A}{d} \right\rfloor \left\lfloor \frac{B}{d} \right\rfloor.
\end{aligned}
于是：
F_{0,2}(A,B,C) = \left( \prod\limits_{d = 1}^{\min(A,B)} G(d) \uparrow \left( \left\lfloor \frac{A}{d} \right\rfloor \left\lfloor \frac{B}{d} \right\rfloor \right) \right) \uparrow C.
其中：
G(n) = \begin{cases}q, & n = q^c, \, q \in \mathbb{P}, \, c \in \mathbb{N}_{+}, \\ 1, & \text{otherwise}.\end{cases}
预处理出 G 的前缀积后数论分块即可，复杂度 \mathcal{O}(\sqrt{n} \log n) 。
考虑 F_{1,1}(A,B,C) ：
F_{1,1}(A,B,C) = \prod\limits_{i = 1}^{A} \prod\limits_{j = 1}^{B} \prod\limits_{k = 1}^{C} i^{ijk}.
两边取对数：
\ln F_{1,1}(A,B,C) &= \sum\limits_{i = 1}^{A} \sum\limits_{j = 1}^{B} \sum\limits_{k = 1}^{C} ijk \ln i\\
&= \sum\limits_{j = 1}^{B} j \sum\limits_{k = 1}^{C} k \sum\limits_{i = 1}^{A} i \ln i\\
&= S(B) S(C) \sum\limits_{i = 1}^{A} i \ln i.
\end{aligned}
其中 S(n) = \displaystyle{\sum\limits_{i = 1}^{n} i} = \displaystyle{\frac{n(n + 1)}{2}} 。
于是：
F_{1,1}(A,B,C) = \left( \prod\limits_{i = 1}^{A} i^i \right) \uparrow \left( S(B) S(C) \right).
预处理出 \displaystyle{\prod\limits_{i = 1}^{n} i^i} 后即可 \mathcal{O}(\log n) 求解。
考虑 F_{1,2}(A,B,C) ：
F_{1,2}(A,B,C) = \prod\limits_{i = 1}^{A} \prod\limits_{j = 1}^{B} \prod\limits_{k = 1}^{C} (\gcd(i,j))^{ijk}.
两边取对数：
\ln F_{1,2}(A,B,C) &= \sum\limits_{i = 1}^{A} \sum\limits_{j = 1}^{B} \sum\limits_{k = 1}^{C} ijk \ln \gcd(i,j)\\
&= \sum\limits_{k = 1}^{C} k \sum\limits_{i = 1}^{A} \sum\limits_{j = 1}^{B} ij \ln(\gcd(i,j))\\
&= S(C) \sum\limits_{i = 1}^{A} \sum\limits_{j = 1}^{B} ij \sum\limits_{d \mid \gcd(i,j)} \Lambda(d)\\
&= S(C) \sum\limits_{i = 1}^{A} \sum\limits_{j = 1}^{B} ij \sum\limits_{\substack{d \mid i \\ d \mid j}} \Lambda(d)\\
&= S(C) \sum\limits_{d = 1}^{\min(A,B)} \Lambda(d) \sum\limits_{\substack{i = 1 \\ d \mid i}}^{A} i \sum\limits_{\substack{j = 1 \\ d \mid j}}^{B} j\\
&= S(C) \sum\limits_{d = 1}^{\min(A,B)} \Lambda(d) \sum\limits_{p = 1}^{\left\lfloor \frac{A}{d} \right\rfloor} dp \sum\limits_{q = 1}^{\left\lfloor \frac{B}{d} \right\rfloor} dq\\
&= S(C) \sum\limits_{d = 1}^{\min(A,B)} d^2 \Lambda(d) \sum\limits_{p = 1}^{\left\lfloor \frac{A}{d} \right\rfloor} p \sum\limits_{q = 1}^{\left\lfloor \frac{B}{d} \right\rfloor} q\\
&= S(C) \sum\limits_{d = 1}^{\min(A,B)} d^2 \Lambda(d) S \left( \left\lfloor \frac{A}{d} \right\rfloor \right) S \left( \left\lfloor \frac{B}{d} \right\rfloor \right).
\end{aligned}
于是：
F_{1,2}(A,B,C) = \left( \prod\limits_{d = 1}^{\min(A,B)} \left( G(d) \uparrow \left( d^2 \right) \right) \uparrow\left( S \left( \left\lfloor \frac{A}{d} \right\rfloor \right) S \left( \left\lfloor \frac{B}{d} \right\rfloor \right) \right) \right) \uparrow S(C).
预处理出 G(n) \uparrow \left( n^2 \right) 的前缀积后数论分块即可，复杂度 \mathcal{O}(\sqrt{n} \log n) 。
考虑 F_{2,1}(A,B,C) ：
F_{2,1}(A,B,C) = \prod\limits_{i = 1}^{A} \prod\limits_{j = 1}^{B} \prod\limits_{k = 1}^{C} i^{\gcd(i,j,k)}.
两边取对数：
\ln F_{2,1}(A,B,C) &= \sum\limits_{i = 1}^{A} \sum\limits_{j = 1}^{B} \sum\limits_{k = 1}^{C} \gcd(i,j,k) \ln i\\
&= \sum\limits_{i = 1}^{A} \sum\limits_{j = 1}^{B} \sum\limits_{k = 1}^{C} \ln i \sum\limits_{d \mid \gcd(i,j,k)} \varphi(d)\\
&= \sum\limits_{i = 1}^{A} \sum\limits_{j = 1}^{B} \sum\limits_{k = 1}^{C} \ln i \sum\limits_{\substack{d \mid i \\ d \mid j \\ d \mid k}} \varphi(d)\\
&= \sum\limits_{d = 1}^{\min(A,B,C)} \varphi(d) \sum\limits_{\substack{i = 1 \\ d \mid i}}^{A} \ln i \sum\limits_{j = 1}^{B} [d \mid j] \sum\limits_{k = 1}^{C} [d \mid k]\\
&= \sum\limits_{d = 1}^{\min(A,B,C)} \varphi(d) \sum\limits_{p = 1}^{\left\lfloor \frac{A}{d} \right\rfloor} \ln (dp) \left\lfloor \frac{B}{d} \right\rfloor \left\lfloor \frac{C}{d} \right\rfloor.
\end{aligned}
于是：
F_{2,1}(A,B,C) &= \prod\limits_{d = 1}^{\min(A,B,C)} \prod\limits_{p = 1}^{\left\lfloor \frac{A}{d} \right\rfloor} (dp) \uparrow \left( \varphi(d) \left\lfloor \frac{B}{d} \right\rfloor \left\lfloor \frac{C}{d} \right\rfloor \right)\\
&= \prod\limits_{d = 1}^{\min(A,B,C)} \left( \left( d \uparrow \left\lfloor \frac{A}{d} \right\rfloor \right) \left( \left\lfloor \frac{A}{d} \right\rfloor ! \right) \right) \uparrow \left( \varphi(d) \left\lfloor \frac{B}{d} \right\rfloor \left\lfloor \frac{C}{d} \right\rfloor \right)\\
&= \prod\limits_{d = 1}^{\min(A,B,C)} \left( \left( d \uparrow \varphi(d) \right) \uparrow \left( \left\lfloor \frac{A}{d} \right\rfloor \left\lfloor \frac{B}{d} \right\rfloor \left\lfloor \frac{C}{d} \right\rfloor \right) \right) \left( \left( \left( \left\lfloor \frac{A}{d} \right\rfloor ! \right) \uparrow \left( \left\lfloor \frac{B}{d} \right\rfloor \left\lfloor \frac{C}{d} \right\rfloor \right) \right) \uparrow \varphi(d) \right)\\
&= \, H_0(A,B,C) \, H_1(A,B,C).
\end{aligned}
其中：
H_0(A,B,C) &= \prod\limits_{d = 1}^{\min(A,B,C)} \left( d \uparrow \varphi(d) \right) \uparrow \left( \left\lfloor \frac{A}{d} \right\rfloor \left\lfloor \frac{B}{d} \right\rfloor \left\lfloor \frac{C}{d} \right\rfloor \right),\\
H_1(A,B,C) &= \prod\limits_{d = 1}^{\min(A,B,C)} \left( \left( \left\lfloor \frac{A}{d} \right\rfloor ! \right) \uparrow \left( \left\lfloor \frac{B}{d} \right\rfloor \left\lfloor \frac{C}{d} \right\rfloor \right) \right) \uparrow \varphi(d).
\end{aligned}
考虑 F_{2,2}(A,B,C) ：
F_{2,2}(A,B,C) = \prod\limits_{i = 1}^{A} \prod\limits_{j = 1}^{B} \prod\limits_{k = 1}^{C} (\gcd(i,j))^{\gcd(i,j,k)}.
两边取对数：
\ln F_{2,2}(A,B,C) &= \sum\limits_{i = 1}^{A} \sum\limits_{j = 1}^{B} \sum\limits_{k = 1}^{C} \gcd(i,j,k) \ln \gcd(i,j)\\
&= \sum\limits_{d = 1}^{\min(A,B)} \ln d \sum\limits_{i = 1}^{A} \sum\limits_{j = 1}^{B} [\gcd(i,j) = d] \sum\limits_{k = 1}^{C} \gcd(d,k)\\
&= \sum\limits_{d = 1}^{\min(A,B)} \ln d \sum\limits_{p = 1}^{\left\lfloor \frac{A}{d} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{B}{d} \right\rfloor} [\gcd(p,q) = 1] \sum\limits_{k = 1}^{C} \gcd(d,k)\\
&= \sum\limits_{d = 1}^{\min(A,B)} \ln d \sum\limits_{p = 1}^{\left\lfloor \frac{A}{d} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{B}{d} \right\rfloor} \sum\limits_{t \mid \gcd(p,q)} \mu(t) \sum\limits_{k = 1}^{C} \gcd(d,k)\\
&= \sum\limits_{d = 1}^{\min(A,B)} \ln d \sum\limits_{p = 1}^{\left\lfloor \frac{A}{d} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{B}{d} \right\rfloor} \sum\limits_{\substack{t \mid p \\ t \mid q}} \mu(t) \sum\limits_{k = 1}^{C} \gcd(d,k)\\
&= \sum\limits_{d = 1}^{\min(A,B)} \ln d \sum\limits_{t = 1}^{\left\lfloor \frac{\min(A,B)}{d} \right\rfloor} \mu(t) \sum\limits_{p = 1}^{\left\lfloor \frac{A}{d} \right\rfloor} [t \mid p] \sum\limits_{q = 1}^{\left\lfloor \frac{B}{d} \right\rfloor} [t \mid q] \sum\limits_{k = 1}^{C} \gcd(d,k)\\
&= \sum\limits_{d = 1}^{\min(A,B)} \ln d \sum\limits_{t = 1}^{\left\lfloor \frac{\min(A,B)}{d} \right\rfloor} \mu(t) \left\lfloor \frac{A}{dt} \right\rfloor \left\lfloor \frac{B}{dt} \right\rfloor \sum\limits_{k = 1}^{C} \gcd(d,k)\\
&= \sum\limits_{d = 1}^{\min(A,B)} \ln d \sum\limits_{t = 1}^{\left\lfloor \frac{\min(A,B)}{d} \right\rfloor} \mu(t) \left\lfloor \frac{A}{dt} \right\rfloor \left\lfloor \frac{B}{dt} \right\rfloor \sum\limits_{k = 1}^{C} \sum\limits_{s \mid \gcd(d,k)} \varphi(s)\\
&= \sum\limits_{d = 1}^{\min(A,B)} \ln d \sum\limits_{t = 1}^{\left\lfloor \frac{\min(A,B)}{d} \right\rfloor} \mu(t) \left\lfloor \frac{A}{dt} \right\rfloor \left\lfloor \frac{B}{dt} \right\rfloor \sum\limits_{k = 1}^{C} \sum\limits_{\substack{s \mid d \\ s \mid k}} \varphi(s)\\
&= \sum\limits_{s = 1}^{\min(A,B,C)} \varphi(s) \sum\limits_{\substack{d = 1 \\ s \mid d}}^{\min(A,B)} \ln d \sum\limits_{t = 1}^{\left\lfloor \frac{\min(A,B)}{d} \right\rfloor} \mu(t) \left\lfloor \frac{A}{dt} \right\rfloor \left\lfloor \frac{B}{dt} \right\rfloor \sum\limits_{k = 1}^{C} [s \mid k]\\
&= \sum\limits_{s = 1}^{\min(A,B,C)} \varphi(s) \left\lfloor \frac{C}{s} \right\rfloor \sum\limits_{u = 1}^{\left\lfloor \frac{\min(A,B)}{s} \right\rfloor} \ln(su) \sum\limits_{t = 1}^{\left\lfloor \frac{\min(A,B)}{su} \right\rfloor} \mu(t) \left\lfloor \frac{A}{sut} \right\rfloor \left\lfloor \frac{B}{sut} \right\rfloor\\
&= \sum\limits_{s = 1}^{\min(A,B,C)} \varphi(s) \left\lfloor \frac{C}{s} \right\rfloor \sum\limits_{u = 1}^{\left\lfloor \frac{\min(A,B)}{s} \right\rfloor} \ln(su) \sum\limits_{\substack{\ell = 1 \\ u \mid \ell}}^{\left\lfloor \frac{\min(A,B)}{s} \right\rfloor} \mu\left( \frac{\ell}{u} \right) \left\lfloor \frac{A}{s \ell} \right\rfloor \left\lfloor \frac{B}{s \ell} \right\rfloor\\
&= \sum\limits_{s = 1}^{\min(A,B,C)} \varphi(s) \left\lfloor \frac{C}{s} \right\rfloor \sum\limits_{\ell = 1}^{\left\lfloor \frac{\min(A,B)}{s} \right\rfloor} \left\lfloor \frac{A}{s \ell} \right\rfloor \left\lfloor \frac{B}{s \ell} \right\rfloor \sum\limits_{u \mid \ell} \ln(su) \, \mu\left( \frac{\ell}{u} \right).
\end{aligned}
于是：
F_{2,2}(A,B,C) = \prod\limits_{s = 1}^{\min(A,B,C)} \left( \prod\limits_{\ell = 1}^{\left\lfloor \frac{\min(A,B)}{s} \right\rfloor} \left( \prod\limits_{u \mid \ell} (su) \uparrow \, \mu\left( \frac{\ell}{u} \right) \right) \uparrow \left( \left\lfloor \frac{A}{s \ell} \right\rfloor \left\lfloor \frac{B}{s \ell} \right\rfloor \right) \right) \uparrow \left( \varphi(s) \left\lfloor \frac{C}{s} \right\rfloor \right).
考虑 \displaystyle{\prod\limits_{u \mid \ell} (su) \uparrow \, \mu\left( \frac{\ell}{u} \right)} ：
\prod\limits_{u \mid \ell} (su) \uparrow \, \mu\left( \frac{\ell}{u} \right) &= \left( \prod\limits_{u \mid \ell} s \uparrow \, \mu\left( \frac{\ell}{u} \right) \right) \left( \prod\limits_{u \mid \ell} u \uparrow \, \mu\left( \frac{\ell}{u} \right) \right)\\
&= \left( s \uparrow \left( \sum\limits_{u \mid l} \mu\left( \frac{\ell}{u} \right) \right) \right) G(\ell)\\
&= \left( s \uparrow \varepsilon(\ell) \right) G(\ell).
\end{aligned}
于是：
F_{2,2}(A,B,C) &= \prod\limits_{s = 1}^{\min(A,B,C)} \left( \prod\limits_{\ell = 1}^{\left\lfloor \frac{\min(A,B)}{s} \right\rfloor} \left( \left( s \uparrow \varepsilon(\ell) \right) G(\ell) \right) \uparrow \left( \left\lfloor \frac{A}{s \ell} \right\rfloor \left\lfloor \frac{B}{s \ell} \right\rfloor \right) \right) \uparrow \left( \varphi(s) \left\lfloor \frac{C}{s} \right\rfloor \right)\\
&= \prod\limits_{s = 1}^{\min(A,B,C)} \left( \left( s \uparrow \varphi(s) \right) \uparrow \left( \left\lfloor \frac{A}{s} \right\rfloor \left\lfloor \frac{B}{s} \right\rfloor \left\lfloor \frac{C}{s} \right\rfloor \right) \right) \left( \left( \left( \prod\limits_{\ell = 1}^{\left\lfloor \frac{\min(A,B)}{s} \right\rfloor} G(\ell) \uparrow \left( \left\lfloor \frac{A}{s \ell} \right\rfloor \left\lfloor \frac{B}{s \ell} \right\rfloor \right) \right) \uparrow \left\lfloor \frac{C}{s} \right\rfloor \right) \uparrow \varphi(s) \right)\\
&= \, H_0(A,B,C) \, H_2(A,B,C).
\end{aligned}
其中：
H_2(A,B,C) &= \prod\limits_{s = 1}^{\min(A,B,C)} \left( \left( \prod\limits_{\ell = 1}^{\left\lfloor \frac{\min(A,B)}{s} \right\rfloor} G(\ell) \uparrow \left( \left\lfloor \frac{A}{s \ell} \right\rfloor \left\lfloor \frac{B}{s \ell} \right\rfloor \right) \right) \uparrow \left\lfloor \frac{C}{s} \right\rfloor \right) \uparrow \varphi(s)\\
&= \prod\limits_{s = 1}^{\min(A,B,C)} F_{0,2} \left( \left\lfloor \frac{A}{s} \right\rfloor , \left\lfloor \frac{B}{s} \right\rfloor , \left\lfloor \frac{C}{s} \right\rfloor \right) \uparrow \varphi(s).
\end{aligned}
于是：
\mathrm{Ans}_{2} &= \frac{F_{2,1}(A,B,C) \, F_{2,1}(B,A,C)}{F_{2,2}(A,B,C) \, F_{2,2}(A,C,B)}\\
&= \frac{H_0(A,B,C) \, H_1(A,B,C) \, H_0(B,A,C) \, H_1(B,A,C)}{H_0(A,B,C) \, H_2(A,B,C) \, H_0(A,C,B) \, H_2(A,C,B)}\\
&= \frac{H_1(A,B,C) \, H_1(B,A,C)}{H_2(A,B,C) \, H_2(A,C,B)}.
\end{aligned}
最后一步可以约分的原因是 H_0(A,B,C) 的值与 A,B,C 的顺序无关。
于是我们只需要求 H_1(A,B,C) 与 H_2(A,B,C) 。
对于 H_1(A,B,C) ，预处理出 \varphi(n) 的前缀和后，数论分块即可。复杂度 \mathcal{O}(\sqrt{n} \log n) 。
对于 H_2(A,B,C) ，预处理出 G(n) 的前缀积与 \varphi(n) 的前缀和后，两层数论分块即可。复杂度：
T(n) &= \sum\limits_{i = 1}^{\left\lfloor \sqrt{n} \right\rfloor} \mathcal{O} \left( \sqrt{i} \, \log n \right) + \sum\limits_{i = 1}^{\left\lfloor \sqrt{n} \right\rfloor} \mathcal{O} \left( \sqrt{\frac{n}{i}} \, \log n \right)\\
&= \mathcal{O} \left( \log n \int_{1}^{\sqrt{n}} \left( \sqrt{x} + \sqrt{\frac{n}{x}} \right) \, \mathrm{d} x \right)\\
&= \mathcal{O} \left( n^{\frac{3}{4}} \log n \right).
\end{aligned}
我们需要预处理的有：
总复杂度为 \mathcal{O} \left( n \log n + T n^{\frac{3}{4}} \log n \right) 。
:::info[Code]
#include<bits/stdc++.h>
const int N=1e5+10;
using namespace std;
int T;
int TT,TT1;
uint64_t inv,inv1;
int n=1e5;
int A,B,C;
int ans_0,ans_1,ans_2;
int phi[N];
int cnt,p[N];
bool vis[N];
int fac[N],h_fac[N];
int G[N],G_2[N];
inline int read(){
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
return ret*f;
}
namespace qmod{
inline int _add(int x,int y){
x+=y;
return (x>=TT)?(x-TT):x;
}
inline int _sub(int x,int y){
x-=y;
return (x<0)?(x+TT):x;
}
inline int _reduce(int64_t x){
uint64_t q=((__uint128_t)x*inv)>>64;
x-=(int64_t)q*TT;
return (int)((x>=TT)?(x-TT):x);
}
inline int _mul(int x,int y){
return _reduce((int64_t)x*y);
}
}
using namespace qmod;
namespace qmod1{
inline int _add1(int x,int y){
x+=y;
return (x>=TT1)?(x-TT1):x;
}
inline int _sub1(int x,int y){
x-=y;
return (x<0)?(x+TT1):x;
}
inline int _reduce1(int64_t x){
uint64_t q=((__uint128_t)x*inv1)>>64;
x-=(int64_t)q*TT1;
return (int)((x>=TT1)?(x-TT1):x);
}
inline int _mul1(int x,int y){
return _reduce1((int64_t)x*y);
}
}
using namespace qmod1;
int qpow(int x,int y){
int ret=1;
while(y){
if(y&1)ret=_mul(ret,x);
x=_mul(x,x);
y>>=1;
}
return ret;
}
void _init(){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i]){
p[++cnt]=i;
phi[i]=i-1;
}
for(int j=1;j<=cnt&&i*p[j]<=n;j++){
vis[i*p[j]]=1;
if(i%p[j]){
phi[i*p[j]]=phi[i]*(p[j]-1);
}else{
phi[i*p[j]]=phi[i]*p[j];
break;
}
}
}
for(int i=1;i<=n;i++)phi[i]=_add1(phi[i],phi[i-1]);
fac[0]=h_fac[0]=1;
for(int i=1;i<=n;i++)fac[i]=_mul(fac[i-1],i),h_fac[i]=_mul(h_fac[i-1],qpow(i,i));
for(int i=0;i<=n;i++)G[i]=1;
G_2[0]=1;
for(int i=1;i<=cnt;i++)for(int64_t j=p[i];j<=n;j*=p[i])G[j]=p[i];
for(int i=1;i<=n;i++){
G_2[i]=_mul(G_2[i-1],qpow(G[i],_mul1(i,i)));
G[i]=_mul(G[i-1],G[i]);
}
}
int S(int n){
return _reduce1((int64_t)n*(n+1)/2);
}
int F_0_1(int A,int B,int C){
return qpow(fac[A],_mul1(B,C));
}
int F_0_2(int A,int B,int C){
int ret=1;
int n=min(A,B);
for(int l=1,r;l<=n;l=r+1){
r=min(A/(A/l),B/(B/l));
ret=_mul(ret,qpow(_mul(G[r],qpow(G[l-1],TT-2)),_mul1(A/l,B/l)));
}
ret=qpow(ret,C);
return ret;
}
int F_1_1(int A,int B,int C){
return qpow(h_fac[A],_mul1(S(B),S(C)));
}
int F_1_2(int A,int B,int C){
int ret=1;
int n=min(A,B);
for(int l=1,r;l<=n;l=r+1){
r=min(A/(A/l),B/(B/l));
ret=_mul(ret,qpow(_mul(G_2[r],qpow(G_2[l-1],TT-2)),_mul1(S(A/l),S(B/l))));
}
ret=qpow(ret,S(C));
return ret;
}
int H_1(int A,int B,int C){
int ret=1;
int n=min(A,min(B,C));
for(int l=1,r;l<=n;l=r+1){
r=min(A/(A/l),min(B/(B/l),C/(C/l)));
ret=_mul(ret,qpow(qpow(fac[A/l],_mul1(B/l,C/l)),_sub1(phi[r],phi[l-1])));
}
return ret;
}
int H_2(int A,int B,int C){
int ret=1;
int n=min(A,min(B,C));
for(int l=1,r;l<=n;l=r+1){
r=min(A/(A/l),min(B/(B/l),C/(C/l)));
ret=_mul(ret,qpow(F_0_2(A/l,B/l,C/l),_sub1(phi[r],phi[l-1])));
}
return ret;
}
void _solve(){
A=read(),B=read(),C=read();
ans_0=ans_1=ans_2=1;
ans_0=_mul(ans_0,F_0_1(A,B,C));
ans_0=_mul(ans_0,F_0_1(B,A,C));
ans_0=_mul(ans_0,qpow(F_0_2(A,B,C),TT-2));
ans_0=_mul(ans_0,qpow(F_0_2(A,C,B),TT-2));
ans_1=_mul(ans_1,F_1_1(A,B,C));
ans_1=_mul(ans_1,F_1_1(B,A,C));
ans_1=_mul(ans_1,qpow(F_1_2(A,B,C),TT-2));
ans_1=_mul(ans_1,qpow(F_1_2(A,C,B),TT-2));
ans_2=_mul(ans_2,H_1(A,B,C));
ans_2=_mul(ans_2,H_1(B,A,C));
ans_2=_mul(ans_2,qpow(H_2(A,B,C),TT-2));
ans_2=_mul(ans_2,qpow(H_2(A,C,B),TT-2));
printf("%d %d %d\n",ans_0,ans_1,ans_2);
}
signed main(){
T=read(),TT=read();
TT1=TT-1;
inv=(uint64_t)(-TT)/TT+1;
inv1=(uint64_t)(-TT1)/TT1+1;
_init();
while(T--)_solve();
return 0;
}:::
P8570 [JRKSJ R6] 牵连的世界
牵连的世界
\small\textbf{\textsf{\textcolor{0E1D69}{NOI/NOI+/CTS}}}
给定 n,m ，求：
\left( \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \sigma_0(ij) \varphi(ij) \right) \bmod (10^9 + 7).
设 n \le m 。推导中忽略取模。
复杂度分析中视 n,m 同阶。
利用经典结论拆 \sigma_0(ij) 与 \varphi(ij) ：
\mathrm{Ans} &= \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} \frac{\varphi(i) \varphi(j) \gcd(i,j)}{\varphi(\gcd(i,j))} \sum\limits_{\substack{d \mid i \\ d \mid j}} \mu(d) \sigma_0 \left( \frac{i}{d} \right) \sigma_0 \left( \frac{j}{d} \right)\\
&= \sum\limits_{d = 1}^{n} \mu(d) \sum\limits_{\substack{i = 1 \\ d \mid i}}^{n} \sum\limits_{\substack{j = 1 \\ d \mid j}}^{m} \frac{\varphi(i) \varphi(j) \gcd(i,j)}{\varphi(\gcd(i,j))} \sigma_0 \left( \frac{i}{d} \right) \sigma_0 \left( \frac{j}{d} \right)\\
&= \sum\limits_{d = 1}^{n} \mu(d) \sum\limits_{p = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{m}{d} \right\rfloor} \frac{\varphi(dp) \varphi(dq) d \gcd(p,q)}{\varphi(d \gcd(p,q))} \sigma_0(p) \sigma_0(q)\\
&= \sum\limits_{d = 1}^{n} \mu(d) \sum\limits_{k = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} \frac{dk}{\varphi(dk)} \sum\limits_{p = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} \sum\limits_{q = 1}^{\left\lfloor \frac{m}{d} \right\rfloor} [\gcd(p,q) = k] \varphi(dp) \varphi(dq) \sigma_0(p) \sigma_0(q)\\
&= \sum\limits_{d = 1}^{n} \mu(d) \sum\limits_{k = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} \frac{dk}{\varphi(dk)} \sum\limits_{u = 1}^{\left\lfloor \frac{n}{dk} \right\rfloor} \sum\limits_{v = 1}^{\left\lfloor \frac{m}{dk} \right\rfloor} [\gcd(u,v) = 1] \varphi(dku) \varphi(dkv) \sigma_0(ku) \sigma_0(kv)\\
&= \sum\limits_{d = 1}^{n} \mu(d) \sum\limits_{k = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} \frac{dk}{\varphi(dk)} \sum\limits_{u = 1}^{\left\lfloor \frac{n}{dk} \right\rfloor} \sum\limits_{v = 1}^{\left\lfloor \frac{m}{dk} \right\rfloor} \varphi(dku) \varphi(dkv) \sigma_0(ku) \sigma_0(kv) \sum\limits_{t \mid \gcd(u,v)} \mu(t)\\
&= \sum\limits_{d = 1}^{n} \mu(d) \sum\limits_{k = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} \frac{dk}{\varphi(dk)} \sum\limits_{u = 1}^{\left\lfloor \frac{n}{dk} \right\rfloor} \sum\limits_{v = 1}^{\left\lfloor \frac{m}{dk} \right\rfloor} \varphi(dku) \varphi(dkv) \sigma_0(ku) \sigma_0(kv) \sum\limits_{\substack{t \mid u \\ t \mid v}} \mu(t)\\
&= \sum\limits_{d = 1}^{n} \mu(d) \sum\limits_{k = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} \frac{dk}{\varphi(dk)} \sum\limits_{t = 1}^{\left\lfloor \frac{n}{dk} \right\rfloor} \mu(t) \sum\limits_{\substack{u = 1 \\ t \mid u}}^{\left\lfloor \frac{n}{dk} \right\rfloor} \varphi(dku) \sigma_0(ku) \sum\limits_{\substack{v = 1 \\ t \mid v}}^{\left\lfloor \frac{m}{dk} \right\rfloor} \varphi(dkv) \sigma_0(kv)\\
&= \sum\limits_{d = 1}^{n} \mu(d) \sum\limits_{k = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} \frac{dk}{\varphi(dk)} \sum\limits_{t = 1}^{\left\lfloor \frac{n}{dk} \right\rfloor} \mu(t) \sum\limits_{x = 1}^{\left\lfloor \frac{n}{dkt} \right\rfloor} \varphi(dktx) \sigma_0(ktx) \sum\limits_{y = 1}^{\left\lfloor \frac{m}{dkt} \right\rfloor} \varphi(dkty) \sigma_0(kty)\\
&= \sum\limits_{d = 1}^{n} \mu(d) \sum\limits_{\substack{\ell = 1 \\ d \mid \ell}}^{n} \frac{\ell}{\varphi(\ell)} \sum\limits_{t = 1}^{\left\lfloor \frac{n}{\ell} \right\rfloor} \mu(t) \sum\limits_{x = 1}^{\left\lfloor \frac{n}{\ell t} \right\rfloor} \varphi(\ell tx) \sigma_0 \left( \frac{\ell tx}{d} \right) \sum\limits_{y = 1}^{\left\lfloor \frac{m}{\ell t} \right\rfloor}\varphi(\ell ty) \sigma_0 \left( \frac{\ell ty}{d} \right)\\
&= \sum\limits_{d = 1}^{n} \mu(d) \sum\limits_{\substack{\ell = 1 \\ d \mid \ell}}^{n} \frac{\ell}{\varphi(\ell)} \sum\limits_{\substack{s = 1 \\ \ell \mid s}}^{n} \mu \left( \frac{s}{\ell} \right) \sum\limits_{x = 1}^{\left\lfloor \frac{n}{s} \right\rfloor} \varphi(sx) \sigma_0 \left( \frac{sx}{d} \right) \sum\limits_{y = 1}^{\left\lfloor \frac{m}{s} \right\rfloor} \varphi(sy) \sigma_0 \left( \frac{sy}{d} \right)\\
&= \sum\limits_{d = 1}^{n} \mu(d) \sum\limits_{\substack{\ell = 1 \\ d \mid \ell}}^{n} \frac{\ell}{\varphi(\ell)} \sum\limits_{\substack{s = 1 \\ \ell \mid s}}^{n} \mu \left( \frac{s}{\ell} \right) \sum\limits_{\substack{i = 1 \\ s \mid i}}^{n} \varphi(i) \sigma_0 \left( \frac{i}{d} \right) \sum\limits_{\substack{j = 1 \\ s \mid j}}^{m} \varphi(j) \sigma_0 \left( \frac{j}{d} \right).
\end{aligned}
考虑对于每个 d ，求出：
F(d) = \sum\limits_{\substack{\ell = 1 \\ d \mid \ell}}^{n} \frac{\ell}{\varphi(\ell)} \sum\limits_{\substack{s = 1 \\ \ell \mid s}}^{n} \mu \left( \frac{s}{\ell} \right) \sum\limits_{\substack{i = 1 \\ s \mid i}}^{n} \varphi(i) \sigma_0 \left( \frac{i}{d} \right) \sum\limits_{\substack{j = 1 \\ s \mid j}}^{m} \varphi(j) \sigma_0 \left( \frac{j}{d} \right).
设：
G_1(s,d) &= \sum\limits_{\substack{i = 1 \\ s \mid i}}^{n} \varphi(i) \sigma_0 \left( \frac{i}{d} \right),\\
G_2(s,d) &= \sum\limits_{\substack{j = 1 \\ s \mid j}}^{m} \varphi(j) \sigma_0 \left( \frac{j}{d} \right).
\end{aligned}
考虑在 d 的倍数上做 Dirichlet 后缀和，分别求出所有 s \in [1,n] \, \land d \mid s 的 G_1(s,d) 与所有 s \in [1,m] \, \land d \mid s 的 G_2(s,d) 。复杂度 \mathcal{O} \left( \dfrac{n}{d} \log \log \dfrac{n}{d} \right) 。
于是：
F(d) = \sum\limits_{\substack{\ell = 1 \\ d \mid \ell}}^{n} \frac{\ell}{\varphi(\ell)} \sum\limits_{\substack{s = 1 \\ \ell \mid s}}^{n} \mu \left( \frac{s}{\ell} \right) G_1(s,d) G_2(s,d).
设：
H(\ell,d) = \sum\limits_{\substack{s = 1 \\ \ell \mid s}}^{n} \mu \left( \frac{s}{\ell} \right) G_1(s,d) G_2(s,d).
在 d 的倍数上做 Dirichlet 后缀差分，求出所有 \ell \in [1,n] \, \land \ell \mid s 的 H(\ell,d) 。复杂度 \mathcal{O} \left( \dfrac{n}{d} \log \log \dfrac{n}{d} \right) 。
于是：
F(d) = \sum\limits_{\substack{\ell = 1 \\ d \mid \ell}}^{n} \frac{\ell}{\varphi(\ell)} H(\ell,d).
预处理出 \dfrac{\ell}{\varphi(\ell)} 后，直接计算的复杂度为 \mathcal{O} \left( \dfrac{n}{d} \right) 。
最终：
\mathrm{Ans} = \sum\limits_{d = 1}^{n} \mu(d) F(d).
时间复杂度：
T(n) &= \sum\limits_{d = 1}^{n} \mathcal{O} \left( \frac{n}{d} \log \log \frac{n}{d} \right)\\
&= \mathcal{O} \left( \log \log n \int_{1}^{n} \frac{n}{x}\, \mathrm{d} x \right)\\
&= \mathcal{O}(n \log n \log \log n).
\end{aligned}
:::info[Code]
#include<bits/stdc++.h>
const int N=3e6+10;
const int TT=1e9+7;
const uint64_t inv=(uint64_t)(-TT)/TT+1;
using namespace std;
int n,m,ans;
int phi[N];
int mu[N];
int tmp[N],sig_0[N];
int cnt,p[N];
bool vis[N];
int _inv[N];
int id_phi[N];
int t_1[N],t_2[N];
inline int read(){
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
return ret*f;
}
namespace qmod{
inline int _add(int x,int y){
x+=y;
return (x>=TT)?(x-TT):x;
}
inline int _sub(int x,int y){
x-=y;
return (x<0)?(x+TT):x;
}
inline int _reduce(int64_t x){
uint64_t q=((__uint128_t)x*inv)>>64;
x-=(int64_t)q*TT;
return (int)((x>=TT)?(x-TT):x);
}
inline int _mul(int x,int y){
return _reduce((int64_t)x*y);
}
}
using namespace qmod;
void _init(){
phi[1]=mu[1]=sig_0[1]=1;
for(int i=2;i<=m;i++){
if(!vis[i]){
p[++cnt]=i;
phi[i]=i-1;
mu[i]=TT-1;
tmp[i]=sig_0[i]=2;
}
for(int j=1;j<=cnt&&i*p[j]<=m;j++){
vis[i*p[j]]=1;
if(i%p[j]){
phi[i*p[j]]=phi[i]*(p[j]-1);
mu[i*p[j]]=_reduce(TT-mu[i]);
tmp[i*p[j]]=2;
sig_0[i*p[j]]=sig_0[i]*2;
}else{
phi[i*p[j]]=phi[i]*p[j];
mu[i*p[j]]=0;
tmp[i*p[j]]=tmp[i]+1;
sig_0[i*p[j]]=sig_0[i]/tmp[i]*(tmp[i]+1);
break;
}
}
}
_inv[1]=1;
for(int i=2;i<=n;i++)_inv[i]=_mul(TT-TT/i,_inv[TT%i]);
for(int i=1;i<=n;i++)id_phi[i]=_mul(i,_inv[phi[i]]);
}
int F(int d){
int ret=0;
int _n=n/d,_m=m/d;
for(int i=1;i<=_n;i++)t_1[i]=_mul(phi[i*d],sig_0[i]);
for(int i=1;i<=_m;i++)t_2[i]=_mul(phi[i*d],sig_0[i]);
for(int i=1;i<=cnt&&p[i]<=_n;i++){
int _p=p[i];
for(int j=_n/_p;j>=1;j--){
t_1[j]=_add(t_1[j],t_1[_p*j]);
}
}
for(int i=1;i<=cnt&&p[i]<=_m;i++){
int _p=p[i];
for(int j=_m/_p;j>=1;j--){
t_2[j]=_add(t_2[j],t_2[_p*j]);
}
}
for(int i=1;i<=_n;i++)t_1[i]=_mul(t_1[i],t_2[i]);
for(int i=1;i<=cnt&&p[i]<=_n;i++){
int _p=p[i],_n_p=_n/_p;
for(int j=1;j<=_n_p;j++){
t_1[j]=_sub(t_1[j],t_1[_p*j]);
}
}
for(int i=1;i<=_n;i++)ret=_add(ret,_mul(id_phi[i*d],t_1[i]));
return ret;
}
signed main(){
n=read(),m=read();
if(n>m)swap(n,m);
_init();
for(int d=1;d<=n;d++)if(mu[d])ans=_add(ans,_mul(mu[d],F(d)));
printf("%d\n",ans);
return 0;
}:::