仅入门，仅是一篇学习小记，仅记录做题时的想法和过程，可能会有些许错误。
题单
莫比乌斯反演
对于一些函数 f(n) ，如果很难直接求出它的值，而容易求出其倍数和或约数和 g(n)，那么可以通过莫比乌斯反演简化运算，求得 f(n) 的值。
前置知识
艾佛森括号
[P] = \begin{cases} 1 &\text{If P is true}\\ 0 &\text{Otherwise} \end{cases}
此处 P 是一个可真可假的命题。
数论分块
引理
\forall a,b,c\in \mathbb{Z},\left\lfloor\dfrac{a}{bc}\right\rfloor = \left\lfloor{\dfrac{\left\lfloor\dfrac{a}{b}\right\rfloor}{c}}\right\rfloor
证明：
\dfrac{a}{b} = \left\lfloor{\dfrac{a}{b}}\right\rfloor + r(0\le r < 1)
\left\lfloor\dfrac{a}{bc}\right\rfloor = \left\lfloor\dfrac{a}{b}\times\dfrac{1}{c}\right\rfloor = \left\lfloor{\dfrac{1}{c}\times\left({\left\lfloor{\dfrac{a}{b}}\right\rfloor + r}\right)}\right\rfloor = \left\lfloor{\dfrac{\left\lfloor\dfrac{a}{b}\right\rfloor}{c} + \dfrac{r}{c}}\right\rfloor = \left\lfloor{\dfrac{\left\lfloor{\dfrac{a}{b}}\right\rfloor}{c}}\right\rfloor
形式一
求：
\sum\limits_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor
对于每一个 \left\lfloor\frac{n}{i}\right\rfloor 我们可以通过打表可以发现：有许多 \left\lfloor\frac{n}{i}\right\rfloor 的值是一样的，而且它们呈一个块状分布。
我们发现对于每一个值相同的块，它的最后一个数就是\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}。
得出这个结论后，我们就可以做的 O(\sqrt{n}) 处理了。
for(int l = 1, r;l <= n; l = r + 1)
{
r = n / (n / l);
ans += (r - l + 1) * (n / l);
}
形式二
给定 k，求：
\sum\limits_{i=1}^{n}k \bmod i
显然，上式等于：
\sum\limits_{i=1}^{n}k - i \cdot \left\lfloor\frac{k}{i}\right\rfloor
可以转化为：
n \cdot k-\sum\limits_{i=1}^{n}i \cdot \left\lfloor\frac{k}{i}\right\rfloor
时间复杂度 \mathcal O(\sqrt{n})。
CODE
形式三
求：
\sum\limits_{i=1}^{n}f(i) \cdot \left\lfloor\frac{n}{i}\right\rfloor
对前半段的函数维护一个前缀和，再利用整除分块处理式子的后半段，处理答案的时候，把两段相乘即可。
例题
P3935 Calculating
若 x 分解质因数结果为 x=\prod\limits_{i=1}^{z}{p_i}^{k_i}，令 f(x)=\prod\limits_{i=1}^{z}(k_i+1)。
求 \sum\limits_{i=l}^{r}f(i) 对 998244353 取模的结果。
上面的可以简化为：
ans=\sum\limits_{i=1}^{r}f(i)-\sum\limits_{j=1}^{l-1}f(j)
考虑如何求 \sum\limits_{i=1}^{r}f(i)，对于 [1,r] 的整数 k，k 作为因数在 [1,r] 中出现了 \left\lfloor\frac{r}{k}\right\rfloor 次，显然对答案的贡献为 \left\lfloor\frac{r}{k}\right\rfloor。
则：
ans=\sum\limits_{i=1}^{r}\left\lfloor\frac{r}{i}\right\rfloor-\sum\limits_{j=1}^{l-1}\left\lfloor\frac{l-1}{j}\right\rfloor
最后再数论分块即可。
时间复杂度 \mathcal O(\sqrt{n})。
CODE
P2260 [清华集训2012]模积和
求：
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}(n \bmod i) \times (m \bmod j),i \ne j
膜 19940417 的值。
首先，不妨设 n \leq m。
显然，上式可简化为：
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}(n \bmod i)\times (m \bmod j)-\sum\limits_{i=1}^{n}(n \bmod i) \times (m \bmod i)
将两个求和拆开，有：
\sum\limits_{i=1}^{n}(n\bmod i)\times\sum\limits_{j=1}^{m}(m \bmod j)-\sum\limits_{i=1}^{n}(n \bmod i)(m \bmod i)
根据取模的定义，a \bmod b=a-b \times \left\lfloor\frac{a}{b}\right\rfloor，将上式转换为：
\sum\limits_{i=1}^{n}(n-i\times \left\lfloor\frac{n}{i}\right\rfloor)\times\sum\limits_{j=1}^{m}(m - j \times \left\lfloor\frac{m}{j}\right\rfloor)-\sum\limits_{i=1}^{n}(n-i \times \left\lfloor\frac{n}{i}\right\rfloor)\times(m-i\times \left\lfloor\frac{m}{i}\right\rfloor)
将括号拆开，可以得到：
(n^2-\sum\limits_{i=1}^{n}i \times \left\lfloor\frac{n}{i}\right\rfloor)\times(m^2-\sum\limits_{j=1}^{m}j \times \left\lfloor\frac{m}{j}\right\rfloor)-\sum\limits_{i=1}^{n}(nm-mi\times\left\lfloor\frac{n}{i}\right\rfloor-ni\times\left\lfloor\frac{m}{i}\right\rfloor+i^2\times\left\lfloor\frac{n}{i}\right\rfloor\times\left\lfloor\frac{m}{i}\right\rfloor)
最后再数论分块即可。
时间复杂度 \mathcal O(\sqrt{n})。
需要注意一下除法取模的问题（用逆元）。
CODE
积性函数
定义
如果一个数论函数 f(n) 满足 f(pq)=f(p)\times f(q),\gcd(p,q)=1，则称 f(n) 是一个积性函数。
特别的，如果不要求 \gcd(p,q)=1 且依然满足上述式子的话，则称 f(n) 是一个完全积性函数。
性质
若 f(n) 和 g(n) 都是积性函数，，则以下函数也为积性函数：
\begin{aligned}
& h(x) = f(x^p)\\
& h(x) = f^p(x)\\
& h(x) = f(x)g(x)\\
& h(x) = \sum_{d\mid x} f(d)g\left(\dfrac{x}{d}\right)
\end{aligned}
常见积性函数
- 单位函数 \epsilon(n)=[n=1]。
- 幂函数 Id^k(n)=n^k， id^1(n) 通常简记为 id(n)。
- 常数函数 1(n)=1。
- 因数个数 \operatorname{d}(n) = \sum\limits_{d\mid n} 1。
- 除数函数 \sigma_{k}(n) = \sum\limits_{d\mid n} d^k。
$k=0$ 时为因数个数函数 $\sigma_{0}(n)$。
- 欧拉函数 \varphi(n) = \sum\limits_{i=1}^{n} [\gcd(i,n) = 1]。
- 莫比乌斯函数 \mu(n) = \begin{cases}1 &n=1\\0 &n\ \text{含有平方因子}\\(-1)^k &k\text{为}\ n\ \text{的本质不同质因子个数} \end{cases}。
狄利克雷卷积
定义
定义两个数论函数 f,g 的狄利克雷卷积为：
\large(f\ast g) (n) = \sum_{d\mid n} f(d)g\left(\dfrac{n}{d}\right)
性质
- 显然满足交换律，结合律，分配律。
-
f \ast g = g \ast f
-
(f \ast g) \ast h = f\ast (g\ast h)
-
f\ast (g+h) = f\ast g + f\ast h
-
- 若 f,g 为积性函数，则 f \ast g 为积性函数。
-
-
-
杜教筛
问题描述
求 S(n)=\sum\limits_{i=1}^{n}f(i)，其中 f(i) 为积性函数。
#### 算法解决
显然，线性筛是 $\mathcal O(n)$ 的，过不了。
考虑推数学式子。
构造积性函数 $h,g$，使得 $h=f*g$。
有：
$$
\sum\limits_{i=1}^{n}h(i)=\sum\limits_{i=1}^{n}\sum\limits_{d|i}f(\frac{i}{d})g(d)\\
=\sum\limits_{d=1}^{n}g(d)\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}f(i)\\
=\sum\limits_{d=1}^{n}g(d)S(\left\lfloor\frac{n}{d}\right\rfloor)
$$
因为我们要算的是 $S(n)$，那把这项单独拎出来不就得了。
所以，有：
$$
S(n)=\frac{\sum\limits_{i=1}^{n}h(i)-\sum\limits_{d=2}^{n}g(d)S(\left\lfloor\frac{n}{d}\right\rfloor)}{g(1)}
$$
于是我们只要能快速算出 $h$ 的前缀和就可以了。
#### 练习
##### $\mu$ 的前缀和
因为 $\mu * I=\epsilon$，那么取 $f=\mu,g=I,f*g=\epsilon$。（参考）
```cpp
inline ll GetSumu(int n)
{
if (n <= N)
return sumu[n]; // sumu是提前筛好的前缀和
if (Smu[n])
return Smu[n]; // 记忆化
ll ret = 1ll; // 单位元的前缀和就是 1
for (int l = 2, r; l <= n; l = r + 1)
{
r = n / (n / l);
ret -= (r - l + 1) * GetSumu(n / l);
// (r - l + 1) 就是 I 在 [l, r] 的和
}
return Smu[n] = ret; // 记忆化
}
```
##### $\varphi$ 的前缀和
因为 $\varphi * I =id$，那么取 $f=\varphi,g=I,f*g=id$。（参考）
```cpp
inline ll GetSphi(int n)
{
if (n <= N)
return sump[n]; // 提前筛好的
if (Sphi[n])
return Sphi[n]; // 记忆化
ll ret = 1ll * n * (n + 1) / 2; // f * g = id 的前缀和
for (int l = 2, r; l <= n; l = r + 1)
{
r = n / (n / l);
ret -= (r - l + 1) * GetSphi(n / l);
// 同上，因为两个的 g 都是 I
}
return Sphi[n] = ret; // 记忆化
}
```
**另附一更全面的筛法 [Min_25](https://www.luogu.com.cn/blog/257146/min25-shai-xue-xi-bi-ji)**
## 莫比乌斯函数
### 定义
$\mu$ 为莫比乌斯函数，定义为
$$
\mu(n)=\begin{cases}1 && n=1\\0 &&n \ 含有平方因子 \\ (-1)^k && k\ 为 \ n \ 的本质不同质因子个数 \end{cases}
$$
### 性质
莫比乌斯函数不仅是积性函数，还有如下性质（即 $\mu * 1=\epsilon$）：
$$
\sum\limits_{d|n} \mu(d) = \begin{cases} 1 && n=1 \\ 0 && n \ne 1\end{cases}
$$
### 结论
$$
[\gcd(i,j)=1]=\sum\limits_{d| \gcd(i,j)} \mu(d)
$$
**线性筛**
由于 $\mu$ 函数为积性函数，因此可以线性筛莫比乌斯函数。
```cpp
void getMu()
{
mu[1] = 1;
for (int i = 2; i <= n; ++i)
{
if (!flg[i])
p[++tot] = i, mu[i] = -1;
for (int j = 1; j <= tot && i * p[j] <= n; ++j)
{
flg[i * p[j]] = 1;
if (i % p[j] == 0)
{
mu[i * p[j]] = 0;
break;
}
mu[i * p[j]] = -mu[i];
}
}
}
```
### 莫比乌斯变换
设 $f(n),g(n)$ 为两个数论函数。
根据 $\mu \ast 1=e$，可以推出 $f=f \ast \epsilon = f\ast(\mu \ast 1)=f \ast \mu \ast 1=(f \ast 1) \ast \mu$。
#### 形式一
如果有：
$$
f(n)=\sum\limits_{d|n}g(d)
$$
那么有：
$$
g(n)=\sum\limits_{d|n} \mu(d)f(\frac{n}{d})
$$
这种形式下，数论函数 $f(n)$ 称为数论函数 $g(n)$ 的莫比乌斯变换，数论函数 $g(n)$ 称为数论函数 $f(n)$ 的莫比乌斯逆变换（反演）。
#### 形式二
如果有：
$$
f(n)=\sum\limits_{n|d}g(d)
$$
那么有：
$$
g(n)=\sum\limits_{n|d} \mu(\frac{d}{n})f(d)
$$
### 常见的几种反演形式
以下默认 $n \le m$。
#### 形式一
$$
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=1]\\
=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{x|i}\sum\limits_{x|j}\mu(x)\\
=\sum\limits_{x=1}^{n}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[x|i][x|j]\mu(x)\\
=\sum\limits_{x=1}^{n}\mu(x)\left\lfloor\frac{n}{x}\right\rfloor\left\lfloor\frac{m}{x}\right\rfloor
$$
数论分块即可 $\mathcal O(n)$ 预处理，$\mathcal O(\sqrt n)$ 单次询问。
#### 形式二
$$
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\gcd(i,j)\\
=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{x|i}^{}\sum\limits_{x|j}^{}\varphi(x)\\
=\sum\limits_{x=1}^{n}\varphi(x)\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[x|i][x|j]\\
=\sum\limits_{x=1}^{n}\varphi(x)\left\lfloor\frac{n}{x}\right\rfloor\left\lfloor\frac{m}{x}\right\rfloor
$$
数论分块即可 $\mathcal O(n)$ 预处理，$\mathcal O(\sqrt n)$ 单次询问。
#### 形式三
$$
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}f(\gcd(i,j))\\
=\sum\limits_{d=1}^{n}f(d)\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=d]\\
=\sum\limits_{d=1}^{n}f(d)\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}[\gcd(i,j)=1]\\
=\sum\limits_{d=1}^{n}f(d)\sum\limits_{k=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu(k)\left\lfloor\frac{n}{dk}\right\rfloor\left\lfloor\frac{m}{dk}\right\rfloor
$$
令 $dk=T$，则：
$$
=\sum\limits_{T=1}^{n}\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor\sum\limits_{d|T}f(d)\mu(\frac{T}{d})
$$
数论分块即可 $\mathcal O(n)$ 预处理，$\mathcal O(\sqrt n)$ 单次询问。
_____
简单证明一下：
$$
\sum_{d=1}^{n}\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}p=\sum_{T=1}^{n}\sum_{p|T}p
$$
有：
$$
\sum_{d=1}^{n}\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}p\\
=\sum_{d=1}^{n}\sum_{p=1}^{n}\frac{p}{d}[d|p]\\
=\sum_{T=1}^{n}\sum_{p|T}p
$$
证毕。
由上，也有：
$$
\sum_{d=1}^{n}\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}pf(d)\\
=\sum_{T=1}^{n}\sum_{p|T}pf(\frac{T}{d})\\
=\sum_{T=1}^{n}\sum_{d|T}\frac{T}{d}f(d)
$$
## 例题
### [SP4491 PGCD - Primes in GCD Table](https://www.luogu.com.cn/problem/SP4491)
求：
$$
\sum\limits_{p \in primes}\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m}[\gcd(x,y)=p]
$$
化简得：
$$
\sum\limits_{p \in primes}\sum\limits_{x=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\sum\limits_{y=1}^{\left\lfloor\frac{m}{p}\right\rfloor}[\gcd(x,y)=1]
$$
根据：
$$
\sum\limits_{d|n} \mu(d) = \begin{cases} 1 && n=1 \\ 0 && n \ne 1\end{cases}
$$
有：
$$
\sum\limits_{p \in primes}\sum\limits_{x=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\sum\limits_{y=1}^{\left\lfloor\frac{m}{p}\right\rfloor}\sum\limits_{k|i,k|j}\mu(k)
$$
先枚举 $k$，有：
$$
\sum\limits_{p \in primes}\sum\limits_{k=1}^{\min(\left\lfloor\frac{n}{p}\right\rfloor,\left\lfloor\frac{m}{p}\right\rfloor)}\sum\limits_{x=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\sum\limits_{y=1}^{\left\lfloor\frac{m}{p}\right\rfloor}\mu(k)[k|i][k|j]
$$
那么就有：
$$
\sum\limits_{p \in primes}\sum\limits_{k=1}^{\min(\left\lfloor\frac{n}{p}\right\rfloor,\left\lfloor\frac{m}{p}\right\rfloor)}\left\lfloor\frac{n}{pk}\right\rfloor\left\lfloor\frac{m}{pk}\right\rfloor\mu(k)
$$
设 $T=pk$，有：
$$
\sum\limits_{T=1}^{\min(n,m)}\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor\sum\limits_{p\in primes,p|T} \mu(\frac{T}{p})
$$
求前缀和再数论分块即可。
[CODE](https://www.luogu.com.cn/paste/s5w11bez)
### [SP26017 GCDMAT - GCD OF MATRIX](https://www.luogu.com.cn/problem/SP26017)
求：
$$
\sum\limits_{i=i_1}^{i_2}\sum\limits_{j=j_1}^{j_2}\gcd(i,j)
$$
考虑容斥，设 $S(n,m)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\gcd(i,j)$，则有：
$$
ans=S(i_2,j_2)-S(i_1-1,j_2)-S(i_2,j_1-1)+S(i_1-1,j_1-1)
$$
单看每一个 $S$，显然有：
$$
\begin{aligned}
&\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\gcd(i,j)\\
&=\sum\limits_{d=1}^{n}d \times\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=d]\\
&=\sum\limits_{d=1}^{n}d\times\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}[\gcd(i,j)=1]\\
&=\sum\limits_{d=1}^{n}d\times\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}\sum\limits_{p|\gcd(i,j)}\mu(p)\\
\end{aligned}
$$
枚举 $p$，有：
$$
\sum\limits_{d=1}^{n}d \times \sum\limits_{p=1}^{\left\lfloor\frac{n}{d}\right\rfloor} \sum\limits_{i=1}^{\left\lfloor\frac{n}{pd}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{pd}\right\rfloor}\sum\limits_{p|\gcd(i,j)}\mu(p)\\
=\sum\limits_{d=1}^{n}\sum\limits_{p=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\left\lfloor\frac{n}{pd}\right\rfloor\left\lfloor\frac{m}{pd}\right\rfloor d \times \mu(p)
$$
设 $T=pd$，有：
$$
\sum\limits_{d=1}^{n}\sum\limits_{p=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor\frac{T}{p}\times\mu(p)
$$
再枚举 $T$，有：
$$
\sum\limits_{T=1}^{n}\sum\limits_{p|T}^{}\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor\frac{T}{p}\times \mu(p)\\
=\sum\limits_{T=1}^{n}\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor\sum\limits_{p|T}^{}\frac{T}{p}\times\mu(p)\\
=\sum\limits_{T=1}^{n}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\varphi(T)
$$
前半部分整除分块，后半部分线性筛即可。
[CODE](https://www.luogu.com.cn/paste/5v822gom)
### [P3327 [SDOI2015]约数个数和](https://www.luogu.com.cn/problem/P3327)
求：
$$
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}d(i \cdot j)
$$
其中，有：
$$
d(n)=\sum\limits_{i|n}1
$$
首先，要了解 $d$ 函数的一个特殊性质：
$$
d(i \cdot j)=\sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x,y)=1]
$$
因此所求为：
$$
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x,y)=1]\\
=\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor[\gcd(x,y)=1]\\
=\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\sum\limits_{p|\gcd(x,y)}\mu(p)\\
=\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\sum\limits_{p=1}^{n}[p|x][p|y]\mu(p)\\
=\sum\limits_{p=1}^{n}\mu(p)\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{p}\rfloor}\lfloor\frac{n}{ip}\rfloor\lfloor\frac{m}{jp}\rfloor\\
=\sum\limits_{p=1}^{n}\mu(p)\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor}\lfloor\frac{n}{ip}\rfloor\sum\limits_{j=1}^{\lfloor\frac{m}{p}\rfloor}\lfloor\frac{m}{jp}\rfloor
$$
[CODE](https://www.luogu.com.cn/paste/gowtmbth)
### [P5221 Product](https://www.luogu.com.cn/problem/P5221)
求：
$$
\prod\limits_{i=1}^{n}\prod\limits_{j=1}^{n}\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)} \pmod{104857601}
$$
$1 \leq n \leq 10^6$。
化简式子，有：
$$
\prod\limits_{i=1}^{n}\prod\limits_{j=1}^{n}\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)}\\
=\prod\limits_{i=1}^{n}\prod\limits_{j=1}^{n}\frac{i \times j}{\gcd(i,j)^2}\\
=\frac{\prod\limits_{i=1}^{n}\prod\limits_{j=1}^{n}i\times j}{\left(\prod\limits_{i=1}^{n}\prod\limits_{j=1}^{n}\gcd(i,j)\right)^2}
$$
先看上面那坨：
$$
\prod_{i=1}^{n}\prod_{j=1}^{n} i\times j\\
=\prod_{i=1}^{n}i^n \times n!\\
=(n!)^n \times \prod\limits_{i=1}^{n}i^n\\
=(n!)^n \times (n!)^n\\
=(n!)^{2n}
$$
然后再看下面那坨：
$$
\prod_{i=1}^{n}\prod_{j=1}^{n}gcd(i,j)\\
=\prod_{d=1}^{n}\prod_{i=1}^{n}\prod_{j=1}^{n}[gcd(i,j)==d]\gcd(i,j)\\
=\prod_{d=1}^{n}d^{\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[gcd(i,j)==d]}\\
==\prod_{d=1}^{n}d^{\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[gcd(i,j)==1]}
$$
先只看指数：
$$
\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[gcd(i,j)==1]\\
=\left(\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\left(2 \times \sum\limits_{j=1}^{i}[\gcd(i,j)=1]\right)\right)-1\\
=2\times \left(\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\varphi(i)\right)-1
$$
所以原式可化为：
$$
\frac{(n!)^{2n}}{\left(\prod\limits_{d=1}^{n}d^{\left(2\times \sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\varphi(i)\right)-1}\right)^2} \pmod{mod}
$$
根据欧拉定理，当 $\gcd(a,m)=1$ 时，有 $a^b=a^{b \ \bmod \ \varphi(m)}\pmod{m}$。
因为模数为质数，所以 $\varphi(m)=m-1$。
所以原式可进一步化为：
$$
\frac{(n!)^{2n}}{\left(\prod\limits_{d=1}^{n}d^{\left(2\times \sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\varphi(i)\right)-1}\bmod (mod-1)\right)^2} \pmod{mod}
$$
[CODE](https://www.luogu.com.cn/paste/z2ktvnl1)
### [P6055 [RC-02] GCD](https://www.luogu.com.cn/problem/P6055)
求：
$$
\sum\limits_{i=1}^n \sum\limits_{j=1}^n \sum\limits_{p=1}^{\lfloor \frac{n}{j}\rfloor} \sum\limits_{q=1}^{\lfloor \frac{n}{j}\rfloor} [\gcd(i,j)=1][\gcd(p,q)=1]
$$
$1 \leq n \leq 2\times 10^9$。
化简式子，有：
$$
\sum\limits_{i=1}^n \sum\limits_{j=1}^n \sum\limits_{p=1}^{\lfloor \frac{n}{j}\rfloor} \sum\limits_{q=1}^{\lfloor \frac{n}{j}\rfloor} [\gcd(i,j)=1][\gcd(p,q)=1]\\
=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{p=1}^{n}\sum\limits_{q=1}^{n}[\gcd(i,j)=1][\gcd(p,q)=j]\\
=\sum\limits_{i=1}^{n}\sum\limits_{p=1}^{n}\sum\limits_{q=1}^{n}[\gcd(i,p,q)=1]\\
=\sum\limits_{i=1}^{n}\sum\limits_{p=1}^{n}\sum\limits_{q=1}^{n}\sum\limits_{d|\gcd(i,p,q)}\mu(d)\\
=\sum\limits_{d=1}^{n}\sum\limits_{i=1}^{n}\sum\limits_{p=1}^{n}\sum\limits_{q=1}^{n}[d|i][d|p][d|q]\mu(d)\\
=\sum\limits_{d=1}^{n}\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{q=1}^{\lfloor\frac{n}{d}\rfloor}\mu(d)\\
=\sum\limits_{d=1}^{n}\mu(d)\lfloor\frac{n}{d}\rfloor^3
$$
用杜教筛维护 $\mu$ 的前缀和即可。
时间复杂度 $\mathcal{O}(n^{\frac{2}{3}})$。
[CODE](https://www.luogu.com.cn/paste/qgda5jo0)
### [P3768 简单的数学题](https://www.luogu.com.cn/problem/P3768)
求：
$$
\sum\limits_{i=1}^{n}\sum_{j=1}^{n}ij\gcd(i,j)
$$
按照套路，化简式子，有：
$$
\begin{aligned}
&\sum\limits_{i=1}^{n}\sum_{j=1}^{n}ij\gcd(i,j)\\
&=\sum\limits_{d=1}^{n}d^3\sum\limits_{i=1}^{n}\sum_{j=1}^{m}\frac{i}{d}\cdot\frac{j}{d}[\gcd(i,j)=d]\\
&=\sum\limits_{d=1}^{n}d^3\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}i\cdot j[\gcd(i,j)=1]\\
&=\sum\limits_{d=1}^{n}d^3\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}i\cdot j\sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)[p|i][p|j]\\
&=\sum\limits_{d=1}^{n}d^3\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}i\cdot j\sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)[p|i][p|j]\\
&=\sum\limits_{d=1}^{n}d^3\sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}i[p|i]\sum\limits_{j=1}^{\lfloor\frac{n}{d}\rfloor}j[p|j]\\
&=\sum\limits_{d=1}^{n}d^3\sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}i[p|i]\sum\limits_{j=1}^{\lfloor\frac{n}{d}\rfloor}j[p|j]\\
&=\sum\limits_{d=1}^{n}d^3\sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\left(\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}i[p|i]\right)^2\\
&=\sum\limits_{d=1}^{n}d^3\sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)p^2s(\lfloor\frac{n}{pd}\rfloor)^2& s(n)=\sum\limits_{i=1}^{n}i=\frac{i \times (i-1)}{2}\\
&=\sum\limits_{T=1}^{n}s(\lfloor\frac{n}{T}\rfloor)^2\sum\limits_{p|T}\mu(p)\left(\frac{T}{p}\right)^3p^2\\
&=\sum\limits_{T=1}^{n}s(\lfloor\frac{n}{T}\rfloor)^2T^2\sum\limits_{p|T}\mu(p)\frac{T}{p}\\
&=\sum_{T=1}^{n}s(\lfloor\frac{n}{T}\rfloor)^2T^2\varphi(T)
\end{aligned}
$$
$\sum\limits_{T=1}^{n}T^2\varphi(T)$ 用杜教筛即可。
[CODE](https://www.luogu.com.cn/paste/0oek5pvh)
### [[CQOI2015]选数](https://www.luogu.com.cn/problem/P3172)
求：
$$
\sum\limits_{a_1=L}^{R}\sum_{a_2=L}^{R}\cdots \sum_{a_n=L}^{R}[\gcd_{i=1}^{n}(a_i)=K]
$$
满足 $1\leq n,K\leq 10^9,1 \leq L \leq R\leq 10^9,R-L\leq 10^5$。
显然，定义 $l=\lceil\frac{L}{K}\rceil,r=\lfloor\frac{R}{K}\rfloor$，原式等于：
$$
\begin{aligned}
&\sum_{a_1=l}^{r}\sum_{a_2=l}^{r}\cdots\sum_{a_n=l}^{r}[\gcd_{i=1}^{n}(a_i)=1]\\
&=\sum_{a_1=l}^{r}\sum_{a_2=l}^{r}\cdots\sum_{a_n=l}^{r}\sum_{p|\gcd\limits_{i=1}^{n}(a_i)}\mu(p)\\
&=\sum_{p=1}^{r}\mu(p)\left(\lfloor\frac{r}{p}\rfloor-\lfloor\frac{l-1}{p}\rfloor\right)^{n}
\end{aligned}
$$
最后杜教筛维护 $\mu$ 的前缀和即可。
[CODE](https://www.luogu.com.cn/paste/f08mdkwz)
### [P4449 于神之怒加强版](https://www.luogu.com.cn/problem/P4449)
求：
$$
\sum\limits_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)^k
$$
按照套路，化简式子，有：
$$
\sum\limits_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)^k\\
=\sum_{d=1}^{n}d^k\sum\limits_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=d]\\
=\sum_{d=1}^{n}d^k\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}[\gcd(i,j)=1]\\
=\sum_{d=1}^{n}d^k\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)[p|i][p|j]\\
\sum_{d=1}^{n}d^k\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}[p|i]\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[p|j]\\
=\sum\limits_{d=1}^{n}d^k\sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\times \lfloor\frac{n}{dp}\rfloor\lfloor\frac{m}{dp}\rfloor\\
=\sum\limits_{T=1}^{n}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{d|T}d^k \mu(\frac{T}{d})\\
$$
设 $g(n)=\sum\limits_{d|n}d^k\mu(\frac{n}{d})$，显然 $g$ 是个乘性函数，线性筛即可。
[CODE](https://www.luogu.com.cn/paste/gy6c0t27)
### [P6825 「EZEC-4」求和](https://www.luogu.com.cn/problem/P6825)
求：
$$
\sum_{i=1}^{n}\sum_{j=1}^{n}\gcd(i,j)^{i+j}
$$
先化简原式，有：
$$
\begin{aligned}
&\sum_{i=1}^{n}\sum_{j=1}^{n}\gcd(i,j)^{i+j}\\
&=\sum_{d=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{n}d^{i+j}[\gcd(i,j)=d]\\
&=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}d^{d\cdot(i+j)}[\gcd(i,j)=1]\\
&=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}d^{d\cdot(i+j)}\sum_{p|\gcd(i,j)}\mu(p)\\
&=\sum_{d=1}^{n}\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}d^{d\cdot(i+j)}[p|i][p|j]\\
&=\sum_{d=1}^{n}\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\sum_{i=1}^{\lfloor\frac{n}{pd}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{pd}\rfloor}d^{dp\cdot(i+j)}\\
&=\sum_{d=1}^{n}\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{T}\rfloor}d^{T\cdot(i+j)} & T=dp\\
&=\sum_{d=1}^{n}\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}(d^T)^i\sum_{j=1}^{\lfloor\frac{n}{T}\rfloor}(d^T)^j\\
&=\sum_{d=1}^{n}\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\left(\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}(d^T)^i\right)^2
\end{aligned}
$$
再看后面那部分，令 $x=\frac{T}{p}^T$。
设 $S_n$ 为等比数列前 $n$ 项和，则有：
$$
S_n=S_{\lfloor\frac{n}{2}\rfloor}(1+a^{\lfloor\frac{n}{2}\rfloor})+a^n[2 \nmid n]
$$
即可 $\mathcal O(\log n)$ 求解。
时间复杂度 $\mathcal O(n \log n)$。
[CODE](https://www.luogu.com.cn/paste/wl82hpcs)
### [P1829 国家集训队Crash的数字表格 / JZPTAB](https://www.luogu.com.cn/problem/P1829)
求（对 $20101009$ 取模）：
$$
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\operatorname{lcm}(i,j)
$$
易得：
$$
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\frac{i \cdot j}{\gcd(i,j)}
$$
枚举最大公因数 $d$，有：
$$
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{d|i,d|j\gcd(\frac{i}{d},\frac{j}{d})=1} \frac{i \cdot j}{d}
$$
又有：
$$
\sum\limits_{d=1}^{\min(n,m)}d\cdot\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}[\gcd(i,j)=1]i\cdot j
$$
由：
$$
\sum\limits_{d|n}\mu(d)=[n=1]
$$
得：
$$
\sum\limits_{d=1}^{\min(n,m)}d\cdot\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}i\cdot j\sum\limits_{a|\gcd(i,j)}\mu(a)
$$
合并得：
$$
\sum\limits_{d=1}^{\min(n,m)}d\cdot\sum\limits_{t=1}^{\left\lfloor\frac{n}{d}\right\rfloor}t^2\mu(t)S(\left\lfloor\frac{n}{dt}\right\rfloor)S(\left\lfloor\frac{m}{dt}\right\rfloor)
$$
其中：
$$
S(n)=\frac{n \cdot (n +1)}{2}
$$
设 $T=dt$，有：
$$
\sum\limits_{T=1}^{\min(n,m)}S(\left\lfloor\frac{n}{T}\right\rfloor)S(\left\lfloor\frac{m}{T}\right\rfloor)\sum\limits_{a|T}a \cdot (\frac{T}{a})^2\mu(\frac{T}{a})
$$
即：
$$
\sum\limits_{T=1}^{\min(n,m)}S(\left\lfloor\frac{n}{T}\right\rfloor)S(\left\lfloor\frac{m}{T}\right\rfloor)T\sum\limits_{b|T}b\mu(b)
$$
设 $f(T)=\sum\limits_{b|T}b \mu(b)$，易知 $f(n)$ 为积性函数，且满足：
$$
f(p)=1-p,f(p^k)=f(p),p \in primes
$$
求前缀和再数论分块即可。
[CODE](https://www.luogu.com.cn/paste/gti3ca59)
### [P6156 简单题](https://www.luogu.com.cn/problem/P6156)
求：
$$
\sum_{i=1}^{n}\sum_{j=1}^{n}(i+j)^k f(\gcd(i,j))\gcd(i,j)
$$
其中 $f$ 函数定义如下：
如果 $k$ 有平方因子 $f(k)=0$，否则 $f(k)=1$。
不难发现 $f(n)=\mu(n)^{2}$。
化简式子，有：
$$
\begin{aligned}&
\sum_{i=1}^{n}\sum_{j=1}^{m}(i+j)^k f(\gcd(i,j))\gcd(i,j)\\
&=\sum\limits_{i=1}^{n}\sum_{j=1}^{n}(i+j)^{k}\mu(\gcd(i,j))^2\gcd(i,j)\\
&=\sum_{d=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{n}(i+j)^k\mu(d)^2d[\gcd(i,j)=d]\\
&=\sum_{d=1}^{n}d^{k+1}\mu(d)^2\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}(i+j)^{k}\sum_{p|\gcd(i,j)}\mu(p)\\
&=\sum_{d=1}^{n}d^{k+1}\mu(d)^2\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}(i+j)^{k}\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)[p|i][p|j]\\
&=\sum_{d=1}^{n}d^{k+1}\mu(d)^2\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\sum_{i=1}^{\lfloor\frac{n}{pd}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{pd}\rfloor}(ip+jp)^{k}\\
&=\sum_{d=1}^{n}d^{k+1}\mu(d)^2\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)p^{k}\sum_{i=1}^{\lfloor\frac{n}{pd}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{pd}\rfloor}(i+j)^{k}\\
&=\sum_{d=1}^{n}d^{k+1}\mu(d)^2\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)p^{k}\operatorname{S}(\lfloor\frac{n}{dp}\rfloor) & S(n)=\sum_{i=1}^{n}\sum_{j=1}^{n}(i+j)^k\\
&=\sum_{T=1}^{n}\operatorname{S}(\lfloor\frac{n}{T}\rfloor)\sum_{d|T}d^{k+1}\mu(d)^2\mu(\frac{T}{d})(\frac{T}{d})^{k}\\
&=\sum_{T=1}^{n}\operatorname{S}(\lfloor\frac{n}{T}\rfloor)\sum_{d|T}d\mu(d)^2\mu(\frac{T}{d})T^k
\end{aligned}
$$
令 $f(n)=\sum\limits_{d|n}d \mu(d)^2 \mu(\frac{n}{d})$。
这显然是积性函数，考虑线性筛。
再看 $\operatorname S(n)$，设 $\operatorname f(n)=\sum\limits_{i=1}^{n}i^k$，$\operatorname g(n)=\sum\limits_{i=1}^{n}\operatorname f(i)$，不难发现：
$$
\operatorname S(n)=\sum\limits_{i=n+1}^{2n}\operatorname f(i)-\sum\limits_{i=1}^{n}\operatorname f(i)=\operatorname g(2\times n)-2\times \operatorname g(n)
$$
预处理即可。
修改一下可过 [加强版](https://www.luogu.com.cn/problem/P6222)。
[P6156 简单题 CODE](https://www.luogu.com.cn/paste/ntrk2ptw)
[P6222 「P6156 简单题」加强版 CODE](https://www.luogu.com.cn/paste/jifphr2p)
### [P6384 『MdOI R2』Quo Vadis](https://www.luogu.com.cn/problem/P6384)
给定一个 **无限大** 的矩阵 $A$，其中 $A_{i,j}=ij\gcd(i,j)$。
接下来有 $m$ 个操作，每行 $1$ 至 $3$ 个整数，意义如下：
* $1$：对矩阵 $A$ 进行高斯消元，使之成为一个上三角矩阵。（**注意**：这里，高斯消元中只允许将一行的某一个倍数加到另一行上，不允许交换任意两行，不允许将某行乘上一个倍数，保证这样之后仍然可以得到上三角矩阵，并且保证消元之后的矩阵的每个元素均为非负整数。）
* $2\ x\ y$：求出当前矩阵的 $A_{x,y}$。
* $3\ x$：求出 $\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{x}A_{i,j}$。
* $4\ x$：设 $B$ 是一个 $x$ 阶矩阵，其中 $B_{i,j}=A_{i,j}$，你需要求出 $\det B$。
**上述所有答案对 $998244353$ 取模**。
首先，对于矩阵 $A$ 满足 $A_{i,j}=i j \gcd(i,j)$，在进行高斯消元后，有：
$$
A'_{i,j}=\begin{cases}i j \varphi(i) && i \mid j \\0 && i \nmid j\end{cases}
$$
对于矩阵 $B$，满足 $B_{i,j}=\gcd(i,j)$，在进行高斯消元后，有：
$$
B'_{i,j}=\begin{cases}\varphi(i) && i \mid j\\0 && i \nmid j\end{cases}
$$
那么，对于 $1$ 操作前的 $2$ 操作答案为 $i j \gcd(i,j)$，对于 $1$ 操作后的 $2$ 操作答案为 $i j \varphi(i)$。
再看 $1$ 操作前的 $3$ 操作，答案为：
$$
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}i j \gcd(i,j)\\
=\sum\limits_{d=1}^{n}d\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}i j [\gcd(i,j)=1]\\
=\sum\limits_{d=1}^{n}d^3\sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{n}{d} \rfloor}i j [\gcd(i,j)=1]\\
=\sum\limits_{d=1}^{n}d^3 \sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{n}{d}\rfloor}i j \sum\limits_{p|\gcd(i,j)}\mu(p)\\
=\sum\limits_{d=1}^{n}d^3\sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor} \mu(p)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{d}\rfloor}i j\\
=\sum\limits_{d=1}^{n}d^3\sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}p^2 \mu(p)\sum\limits_{i=1}^{\lfloor\frac{n}{pd}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{pd}\rfloor}i j\\
=\sum\limits_{d=1}^{n}d^3\sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}p^2 \mu(p)\left(\sum\limits_{i=1}^{\lfloor\frac{n}{pd}\rfloor}i\right)^2\\
\sum\limits_{d=1}^{n}d\sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}(pd)^2 \mu(p)\left(\sum\limits_{i=1}^{\lfloor\frac{n}{pd}\rfloor}i\right)^2
$$
设 $f(n)=\left(\sum\limits_{i=1}^{n}i\right)^2$，则有：
$$
\sum\limits_{d=1}^{n}d\sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}(pd)^2 \mu(p)f(\lfloor\frac{n}{pd}\rfloor)
$$
设 $T=pd$，有：
$$
\sum\limits_{T}^{n}T^2f(\lfloor\frac{n}{T}\rfloor)\sum\limits_{d|T}d \mu(\frac{T}{d})
$$
根据狄利克雷卷积，有：
$$
\sum\limits_{T}^{n}T^2f(\lfloor\frac{n}{T}\rfloor)\varphi(T)
$$
数论分块套杜教筛即可。
对于 $1$ 操作后的 $3$ 操作，设 $g(n)$ 为第 $n$ 列的和，那么有：
$$
g(n)=n\sum\limits_{d|n}d\varphi(d)
$$
设 $h(n)=\sum\limits_{d|n}d \varphi(d)$，显然， $h(n)$ 是个积性函数，线性筛即可。
答案即为：
$$
\sum\limits_{i=1}^{n}g(i)\\
=\sum\limits_{i=1}^{n}\left(i \times h(i)\right)
$$
对于操作 $4$，行列式即消元后主对角线上元素乘积，所以答案即为：
$$
\prod\limits_{i=1}^{n}i^2\varphi(i)
$$
[CODE](https://www.luogu.com.cn/paste/0quklgco)
### [P7486 「Stoi2031」彩虹](https://www.luogu.com.cn/problem/P7486)
令 $S(a,b)=\prod\limits_{i=1}^{a}\prod\limits_{j=1}^{b}\operatorname{lcm}(a,b)^{\operatorname{lcm}(a,b)}$。
求：
$$
\frac{S(r,r)\times S(l-1,l-1)}{S(r,l-1)\times S(l-1,r)}
$$
不妨设 $a \leq b$。
令 $dp=t$，则有：
$$
\begin{aligned}
S(a,b)&=\prod\limits_{i=1}^{a}\prod\limits_{j=1}^{b}\operatorname{lcm}(a,b)^{\operatorname{lcm}(a,b)}\\
&=\prod_{i=1}^{a}\prod_{j=1}^{b}\frac{ij}{\gcd(a,b)}^{(\frac{ij}{\gcd(a,b)})}\\
&=\prod_{d=1}^{a}\prod_{i=1}^{a}\prod_{j=1}^{b}\frac{ij}{d}^{(\frac{ij}{d})[\gcd(i,j)=d]}\\
&=\prod_{d=1}^{a}\prod_{i=1}^{\lfloor\frac{a}{d}\rfloor}\prod_{j=1}^{\lfloor\frac{b}{d}\rfloor}(ijd)^{ijd[\gcd(i,j)=1]}\\
&=\prod_{d=1}^{a}\prod_{i=1}^{\lfloor\frac{a}{d}\rfloor}\prod_{j=1}^{\lfloor\frac{b}{d}\rfloor}(ijd)^{ijd\sum\limits_{p=1}^{\lfloor\frac{a}{d}\rfloor}\mu(p)[p|i][p|j]}\\
&=\prod_{d=1}^{a}\prod_{p=1}^{\lfloor\frac{a}{d}\rfloor}\prod_{i=1}^{\lfloor\frac{a}{d}\rfloor}[p|i]\prod_{j=1}^{\lfloor\frac{b}{d}\rfloor}[p|j](ijd)^{ijd\mu(p)}\\
&=\prod_{d=1}^{a}\prod_{p=1}^{\lfloor\frac{a}{d}\rfloor}\prod_{i=1}^{\lfloor\frac{a}{dp}\rfloor}\prod_{j=1}^{\lfloor\frac{b}{dp}\rfloor}(ijdp^2)^{ijdp^2\mu(p)}\\
&=\prod_{t=1}^{a}\prod_{p|t}\prod_{i=1}^{\lfloor\frac{a}{t}\rfloor}\prod_{j=1}^{\lfloor\frac{b}{t}\rfloor}(ijtp)^{ijtp\mu(p)}\\
\end{aligned}
$$
令 $s(x)=\sum\limits_{i=1}^{x}i=\frac{x(x+1)}{2}$，$f(x)=\prod\limits_{i=1}^{x}i^i$，则有：
$$
\prod_{i=1}^{n}\prod_{j=1}^{m}(ij)^{ij}=f(n)^{s(m)}\times f(m)^{s(n)}
$$
令其为 $G(n,m)$。
另有：
$$
\prod_{i=1}^{n}\prod_{j=1}^{m}(tp)^{ij}=(tp)^{s(n)\times S(m)}
$$
带回原式有：
$$
\prod_{t=1}^{a}\left( \prod_{p|t}\left( G(\lfloor\frac{a}{t}\rfloor,\lfloor\frac{b}{t}\rfloor) \times (tp)^{s(\lfloor\frac{a}{t}\rfloor)\times s(\lfloor\frac{b}{t}\rfloor)} \right)^{p\mu(p)} \right)^{t}
$$
另 $h(x)=\sum\limits_{d|x}d\mu(d),y(x)=\prod\limits_{d|x}d^{d\mu(d)}$，则有：
$$
\prod_{t=1}^{a}G(\lfloor\frac{a}{t}\rfloor,\lfloor\frac{b}{t}\rfloor)^{t \cdot h(t)}\times (t^{h(t)}\times y(t))^{t\times s(\lfloor\frac{a}{t}\rfloor)\times s(\lfloor\frac{b}{t}\rfloor)}
$$
再令 $hh(x)=x\times h(x),yy(x)=(x^{h(x)}\times y(x))^{x}$，可得：
$$
\prod_{t=1}^{a}G(\lfloor\frac{a}{t}\rfloor,\lfloor\frac{b}{t}\rfloor)^{hh(t)}\times yy(t)^{s(\lfloor\frac{a}{t}\rfloor)\times s(\lfloor\frac{b}{t}\rfloor)}
$$
最后前缀和 $\text{+}$ 前缀积 $\text{+}$ 数论分块即可。
再加一个小优化，设一个阈值 $S$，对于 $1 \leq t < S$ 的直接暴力算，因为这部分 $l,r$ 相差较小。
对于 $S \leq t \leq n$ 的，再数论分块算。
[CODE](https://www.luogu.com.cn/paste/dubzw06i)
### [P3704 [SDOI2017]数字表格](https://www.luogu.com.cn/problem/P3704)
求：
$$
\prod\limits_{i=1}^{n}\prod\limits_{j=1}^{m}f_{\gcd(i,j)}
$$
其中 $f$ 表示斐波那契数列。
化简式子，有：
$$
\prod\limits_{i=1}^{n}\prod\limits_{j=1}^{m}f_{\gcd(i,j)}\\
=\prod\limits_{d=1}^{n}\prod\limits_{i=1}^{n}\prod_{j=1}^{n}f_d[\gcd(i,j)=d]\\
=\prod\limits_{d=1}^{n}f_{d}^{\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=d]}\\
=\prod\limits_{d=1}^{n}f_{d}^{\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)=1]}\\
=\prod\limits_{d=1}^{n}f_{d}^{\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum\limits_{p|\gcd(i,j)}\mu(p)}\\
=\prod\limits_{d=1}^{n}f_{d}^{\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)[p|i][p|j]}\\
=\prod\limits_{d=1}^{n}f_{d}^{\sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor}\\
=\prod_{T=1}^{n}\left(\prod\limits_{d|T}f_{d}^{\mu(\frac{T}{d})}\right)^{\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor}\\
$$
令 $F(n)=\prod\limits_{d|n}f_d^{\mu(\frac{n}{d})}$。
则有：
$$
\prod_{T=1}^{n}F(T)^{\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor}
$$
线性筛预处理前缀积即可。
[CODE](https://www.luogu.com.cn/paste/9rvtcv9e)
### [SP26045 GCDMAT2 - GCD OF MATRIX (hard)](https://www.luogu.com.cn/problem/SP26045)
~~最优解，嘿嘿。~~
求：
$$
\sum_{i=i_1}^{i_2}\sum_{j=j_1}^{j_2}\gcd(i,j) \pmod{10^9+7}
$$
$T$ 组数据。
其中，$T \leq 50000,1 \leq i2,j2\leq 10^6$。
首先设 $S(n,m)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\gcd(i,j)$。
则 $ans=S(i_2,j_2)+S(i_1,j_1)-S(i_2,j_1)-S(i_1,j_2)$。
考虑化简 $S(n,m)$，有：
$$
\large
\begin{aligned}
S(n,m)&=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\gcd(i,j)\\
&=\sum_{d=1}^{n}d\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=d]\\
&=\sum_{d=1}^{n}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)=1] \\
&=\sum_{d=1}^{n}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{p|\gcd(i,j)}^{}\mu(p)\\
&=\sum_{d=1}^{n}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)[p|i][p|j] \\
&=\sum_{d=1}^{n}d\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[p|i][p|j] \\
&=\sum_{d=1}^{n}d\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor \\
&=\sum_{d=1}^{n}d\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor \\
&=\sum_{T=1}^{n}\sum_{p|T}\mu(p)\frac{T}{p}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor & 设\ T=dp\\
&=\sum_{T=1}^{n}\varphi(T)\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor \\
\end{aligned}
$$
这是 $\mathcal{O}(T\sqrt{n})$ 的算法，且常数巨大。
考虑优化，发现：
$$
\large
\begin{aligned}
ans=\sum_{i=1}^{n}\varphi(i)(\lfloor\frac{i_2}{i}\rfloor-\lfloor\frac{i_1}{i}\rfloor)(\lfloor\frac{j_2}{i}\rfloor-\lfloor\frac{j_1}{i}\rfloor)&&n=\min(i_2,j_2)
\end{aligned}
$$
但是，还是过不了。
这里有一个好方法：预处理出 $1\sim N$ 的倒数，然后把除法改成乘法，优化常数，可过。
但还可以优化。
考虑根号分治。
我们发现这实际上是一个预处理和查询的平衡，因为我们发现，$l$ 和 $r$ 越大，相同一段长度就越大，暴力的复杂度就相对越劣（意思就是用整除分块处理越快），那么我们可以考虑在 $l$ 和 $r$ 较小的时候暴力，否则预处理。
详见代码。
[CODE](https://www.luogu.com.cn/paste/04i8qct4)
### [P1587 [NOI2016] 循环之美](https://www.luogu.com.cn/problem/P1587)
求 $\sum\limits_{x=1}^n\sum\limits_{y=1}^m\frac{x}{y}$ 在 $k$ 进制下能表示成循环节从第一位小数开始的无限循环小数或整数的最简分数个数。
先思考怎么转换。
首先肯定满足 $\gcd(x,y)=1$。
假设 $\frac{x}{y}$ 的循环节长度为 $l$，根据在 $k$ 进制下的数乘以 $k^p$ 相当于将小数点往后挪 $p$ 位，那么有：
$$
\{\frac{xk^l}{y}\}=\{\frac{x}{y}\}
$$
转换一下上面那个式子，有：
$$
\begin{aligned}
\frac{xk^l}{y}-\lfloor\frac{xk^l}{y}\rfloor&=\frac{x}{y}-\lfloor\frac{x}{y}\rfloor\\
xk^l-\lfloor\frac{xk^l}{y}\rfloor\cdot y&=x-\lfloor\frac{x}{y}\rfloor\cdot y\\
xk^l &\equiv x \pmod y\\
k^l &\equiv 1 \pmod y\\
\gcd(k,y)&=1
\end{aligned}
$$
那么题意就可以转换为求：
$$
\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=1][\gcd(j,k)=1]
$$
先化简原式，有：
$$
\begin{aligned}
&\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=1][\gcd(j,k)=1]\\
&=\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(j,k)=1]\sum_{p|\gcd(i,j)}\mu(p)\\
&=\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(j,k)=1]\sum_{p=1}^{\min(n,m)}\mu(p)[p|i][p|j]\\
&=\sum_{p=1}^{\min(n,m)}\mu(p)\sum_{i=1}^{n}\sum_{j=1}^{m}[p|i][p|j][\gcd(j,k)=1]\\
&=\sum_{p=1}^{\min(n,m)}\mu(p)\sum_{p|i}^{n}\sum_{p|j}^{m}[\gcd(j,k)=1]\\
&=\sum_{p=1}^{\min(n,m)}\mu(p)\lfloor\frac{n}{p}\rfloor\sum_{p|j}^{m}[\gcd(j,k)=1]\\
&=\sum_{p=1}^{\min(n,m)}\mu(p)[\gcd(p,k)=1]\lfloor\frac{n}{p}\rfloor\sum_{p=1}^{\lfloor\frac{m}{p}\rfloor}[\gcd(j,k)=1]\\
\end{aligned}
$$
再设个函数，并化简：
$$
\begin{aligned}
f(n)=\sum_{i=1}^{n}[\gcd(i,k)=1]
\end{aligned}
$$
思考，当 $i>k$ 时，有 $\gcd(i,k)=\gcd(i+k,k)$，那么答案肯定是呈现一个长度为 $k$ 的循环，那么有：
$$
\begin{aligned}
f(n)
&=f(n \bmod k)+\lfloor\frac{n}{k}\rfloor\varphi(k)
\end{aligned}
$$
那么原式等于：
$$
\sum_{p=1}^{\min(n,m)}\lfloor\frac{n}{p}\rfloor f(\lfloor\frac{m}{p}\rfloor)\mu(p)[\gcd(p,k)=1]
$$
现在已经有整除分块了，然后是处理 $\sum\limits_{i=1}^{n}\mu(i)[\gcd(i,k)=1]$ 前缀和的问题。
**法一**
设前面那个式子为 $s(n,k)$。
尝试化简 $s(n,k)$，则有：
$$
\begin{aligned}
s(n,k)&=\sum_{i=1}^{n}\mu(i)[\gcd(i,k)=1]\\
&=\sum_{i=1}^{n}\mu(i)\sum_{p=1}^{\min(n,k)}\mu(p)[p|i][p|k]\\
&=\sum_{p|k}^{\min(n,k)}\mu(p)\sum_{p|i}^{n}\mu(i)\\
&=\sum_{p|k}^{\min(n,k)}\mu(p)\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\mu(ip)\\
&=\sum_{p|k}^{\min(n,k)}\mu(p)^2\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\mu(i)[\gcd(i,p)=1]\\
&=\sum_{p|k}^{\min(n,k)}\mu(p)^2s(\lfloor\frac{n}{p}\rfloor,p)
\end{aligned}
$$
然后数论分块即可。
**法二**
这里是设前面那个式子为 $s(n)$，则有：
$$
\begin{aligned}
s(n)&=\sum_{i=1}^{n}\mu(i)[\gcd(i,k)=1]\\
&=\sum_{i=1}^{n}[\gcd(i,k)=1]s(\lfloor\frac{n}{i}\rfloor)-\sum_{i=2}^{n}[\gcd(i,k)=1]s(\lfloor\frac{n}{i}\rfloor)
\end{aligned}
$$
先看前面那个：
$$
\begin{aligned}
&\sum_{i=1}^{n}[\gcd(i,k)=1]s(\lfloor\frac{n}{i}\rfloor)\\&=\sum_{i=1}^{n}[\gcd(i,k)=1]\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}\mu(j)[\gcd(j,k)=1]\\
&=\sum_{i=1}^{n}\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}\mu(j)[\gcd(ij,k)=1]\\
&=\sum_{t=1}^{n}\sum_{d|t}[\gcd(t,k)=1]\mu(d)\\
&=\sum_{t=1}^{n}[\gcd(t,k)=1][t=1]\\
&=1
\end{aligned}
$$
那么最终有：
$$
s(n)=1-\sum_{i=2}^{n}[\gcd(i,k)=1]s(\lfloor\frac{n}{i}\rfloor)
$$
数论分块即可。
[CODE](https://www.luogu.com.cn/paste/8knxmq1i)
### [P3700 [CQOI2017]小Q的表格](https://www.luogu.com.cn/problem/P3700)
有一个表格，满足：
$$
\begin{aligned}
&f(a,b)=f(b,a)\\
&b \times f(a,a+b)=(a+b)\times f(a,b)
\end{aligned}
$$
且一开始 $f(a,b)=a\times b$，然后带上一个单点修改操作。
每当修改了一个格子的数之后，为了让表格继续满足上述两个条件，你还需要把这次修改能够波及到的全部格子里都改为恰当的数。
你还需要随时输出前 $k$ 行前 $k$ 列这个有限区域内所有数的和 $\pmod {10^9+7}$。
考虑从下面那个式子得出一些可以反演的东西，有：
$$
\begin{aligned}
b \times f(a,a+b)&=(a+b)\times f(a,b)\\
ab \times f(a,a+b)&=a(a+b)\times f(a,b)\\
\frac{f(a,a+b)}{a(a+b)}&=\frac{f(a,b)}{ab}\\
\frac{f(a,b)}{ab}&=\frac{f(\gcd(a,b),\gcd(a,b))}{\gcd(a,b)^2}
\end{aligned}
$$
设 $\gcd(a,b)=d$，则有：
$$
\begin{aligned}
\frac{f(a,b)}{ab}&=\frac{f(d,d)}{d^2}\\
f(a,b)&=\frac{f(d,d)\times ab}{d^2}
\end{aligned}
$$
考虑到这个矩阵要变换，因为修改一个位置 $(a,b)$ 的值后有且仅有 $\gcd(x,y)=d$ 的 $(x,y)$ 位置的 $f$ 值会跟着变化，那么用一个树状数组维护 $f(d,d)$ 即可。
设 $f(d,d)=g(d)$，再考虑答案：
$$
\begin{aligned}
ans&=\sum_{d=1}^{n}g(d)\sum_{i=1}^{n}\sum_{j=1}^{n}\frac{ij}{\gcd(i,j)^2}[\gcd(i,j)=d]\\
&=\sum_{d=1}^{n}g(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}ij[\gcd(i,j)=1]\\
&=\sum_{d=1}^{n}g(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}ij\sum_{p|\gcd(i,j)}\mu(p)\\
&=\sum_{d=1}^{n}g(d)\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p) \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}i[p|i]\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}j[p|j]\\
&=\sum_{d=1}^{n}g(d)\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)p^2\left(\sum_{i=1}^{\lfloor\frac{\lfloor\frac{n}{d}\rfloor}{p}\rfloor}i\right)^2\\
&=\sum_{d=1}^{n}g(d)\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)p^2S(\lfloor\frac{\lfloor\frac{n}{d}\rfloor}{p}\rfloor) ^2
\end{aligned}
$$
设 $G(n)=\sum\limits_{i=1}^{n}i^2\mu(i)S(\lfloor\frac{n}{i}\rfloor)^2$，则原式等于：
$$
\sum_{d=1}^{n}g(d)G(\lfloor\frac{n}{d}\rfloor)
$$
根据 $\lfloor\frac{n}{i}\rfloor-\lfloor\frac{n-1}{i}\rfloor=[i|n]$，有：
$$
\begin{aligned}
G(n)-G(n-1)&=\sum_{i|n}i^2\mu(i)(S(\lfloor\frac{n}{i}\rfloor)^2-S(\lfloor\frac{n}{i}\rfloor-1)^2\\
&=\sum_{i|n}i^2\mu(i)(\frac{n}{i})^3\\
&=n^2\sum_{i|n}\mu(i)\frac{n}{i}\\
&=n^2\varphi(n)
\end{aligned}
$$
那么有：
$$
G(n)=\sum_{i=1}^{n}i^2\varphi(i)
$$
那么原式等于：
$$
\sum_{d=1}^{n}g(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}i^2\varphi(i)
$$
线性筛，维护前缀和，再数论分块即可。
[CODDE](https://www.luogu.com.cn/paste/tnmzwbye)
### [P4240 毒瘤之神的考验](https://www.luogu.com.cn/problem/P4240)
求：
$$
\sum_{i=1}^{n}\sum_{j=1}^{m}\varphi(ij)
$$
先要考虑怎么把 $\varphi$ 转成带有 $\gcd$ 或 $\operatorname{lcm}$ 的形式。
性质：$\varphi(ij)=\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}$。
证明：
$$
\begin{aligned}
\varphi(i)\varphi(j)&=i\prod_{p|i}\frac{p-1}{p}j\prod_{p|j}\frac{p-1}{p} &p\in primes\\
&=ij\prod_{p|ij}\frac{p-1}{p}\prod_{p|\gcd(i,j)}\frac{p-1}{p}
\end{aligned}
$$
所以有：
$$
\begin{aligned}
\varphi(i)\varphi(j)\gcd(i,j)&=ij\prod_{p|ij}\frac{p-1}{p}\gcd(i,j)\prod_{p|\gcd(i,j)}\frac{p-1}{p}\\
&=\varphi(ij)\varphi(\gcd(i,j))
\end{aligned}
$$
化简式子，有：
$$
\begin{aligned}
&\sum_{i=1}^{n}\sum_{j=1}^{m}\varphi(ij)\\
&=\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}\\
&=\sum_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{i=1}^{n}\sum_{j=1}^{m}\varphi(i)\varphi(j)[gcd(i,j)=d]\\
&=\sum_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\varphi(id)\varphi(jd)[gcd(i,j)=1]\\
&= \sum_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\varphi(id)[p|i]\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\varphi(jd)[p|j]\\
&=\sum_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\varphi(ikd)\sum_{j=1}^{\lfloor\frac{m}{kd}\rfloor}\varphi(jkd)\\
&=\sum_{T=1}^{n}\left(\sum_{d|T}\frac{d}{\varphi(d)}\mu(\frac{T}{p})\right)\left(\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\varphi(iT)\right)\left(\sum_{j=1}^{\lfloor\frac{m}{T}\rfloor}\varphi(jT)\right)& 设 \ T=dp \\
\end{aligned}\\
$$
设 $f(n)=\sum\limits_{d|n}\frac{d}{\varphi(d)}\mu(\frac{n}{p})$，线性筛预处理即可，$\mathcal{O}(n \ln n)$。
设 $g(k,n)=\sum\limits_{i=1}^{n}\varphi(i,k)$，显然 $g(k,n)=g(k,n-1)+\varphi(nk)$。
则原式等于：
$$
\begin{aligned}
\sum_{T=1}^{n}f(T)\times g(T,\lfloor\frac{n}{T}\rfloor)\times g(T,\lfloor\frac{m}{T}\rfloor)
\end{aligned}
$$
发现整除分块不了，考虑把整个式子设出来，令：
$$
h(a,b,n)=\sum_{t=1}^{n}f(t)\times g(t,a) \times g(t,b)
$$
容易发现，这其实就是一个整除分块的首尾差分形式：
$$
h(a,b,n)=\sum_{\lfloor\frac{n}{l}\rfloor=\lfloor\frac{n}{r}\rfloor \operatorname{and} \lfloor\frac{m}{l}\rfloor=\lfloor\frac{m}{r}\rfloor}h(\lfloor\frac{n}{r}\rfloor,\lfloor\frac{m}{r}\rfloor,r)-h(\lfloor\frac{n}{r}\rfloor,\lfloor\frac{m}{r}\rfloor,l)
$$
再考虑根号分治，我们设一个阈值 $S$，将所有 $h(1,1,1) \sim h(S,S,n)$ 的 $h$ 值预处理出来。
预处理式子就是：
$$
h(j,k,i)=h(j,k,i-1)+f(i)\times g(i,j)\times g(i,k)
$$
对于 $\lfloor\frac{n}{r}\rfloor \leq S$ 可直接查询。
否则，可知 $r \leq \lfloor\frac{n}{S}\rfloor$，数论分块计算即可。
[CODE](https://www.luogu.com.cn/paste/ka6k1em7)
### [P5572 [CmdOI2019]简单的数论题](https://www.luogu.com.cn/problem/P5572)
求：
$$
\sum_{i=1}^{n}\sum_{j=1}^{m}\varphi(\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)})\bmod 23333
$$
$T$ 组数据，满足 $T \leq 3 \times 10^4,m \leq n \leq 5 \times 10^4$。
下面默认 $n \leq m$。
先化简原式，有：
$$
\begin{aligned}
\sum_{i=1}^{n}\sum_{j=1}^{m}\varphi(\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)})&=\sum_{i=1}^{n}\sum_{j=1}^{m}\varphi(\frac{i \times j}{\gcd(i,j)^2})\\
&=\sum_{d=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{m}\varphi(\frac{i \times j}{d^2})[\gcd(i,j)=d]\\
&=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\varphi(i\times j)[\gcd(i,j)=1]\\
&=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\varphi(i)\varphi(j)[\gcd(i,j)=1]\\
&=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\varphi(i)\varphi(j)\sum_{p|\gcd(i,j)}\mu(p)\\
&=\sum_{d=1}^{n}\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p) \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\varphi(i)\varphi(j)[p|i][p|j]\\
&=\sum_{d=1}^{n}\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p) \sum_{i=1}^{\lfloor\frac{n}{pd}\rfloor}\varphi(ip)\sum_{j=1}^{\lfloor\frac{m}{pd}\rfloor}\varphi(jp)\\
&=\sum_{T=1}^{n}\sum_{p|T}\mu(p)\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\varphi(ip)\sum_{j=1}^{\lfloor\frac{m}{T}\rfloor}\varphi(jp)
\end{aligned}
$$
设：
$$
G(x,y)=\sum_{i=1}^{x}\varphi(iy)
$$
暴力预处理即可。
那么原式等于：
$$
\sum_{T=1}^{n}\sum_{p|T}\mu(p)G(\lfloor\frac{n}{T}\rfloor,p)G(\lfloor\frac{m}{T}\rfloor,p)
$$
再设：
$$
H(x,y,z)=\sum_{i=1}^{z}\sum_{p|i}\mu(p)G(x,p)g(y,p)
$$
然后跟 [P4240 毒瘤之神的考验](https://www.luogu.com.cn/problem/P4240) 差不多，将答案表示为关于 $H$ 的差分加下取整的形式。
再考虑根号分治，我们设一个阈值，将所有范围内的 $H$ 值递推预处理出来。
后面的再数论分块算。
[CODE](https://www.luogu.com.cn/paste/p9sty37n)
### [P5518 [MtOI2019]幽灵乐团 / 莫比乌斯反演基础练习题](https://www.luogu.com.cn/problem/P5518)
关于本题的一种**特别**简便的做法 [「题解」Luogu P5518 [MtOI2019]幽灵乐团 / 莫比乌斯反演基础练习题](https://www.cnblogs.com/mangoworld/p/Solution-Luogu-P5518.html)
求：
$$
\prod\limits_{i=1}^{A}\prod\limits_{j=1}^{B}\prod\limits_{k=1}^{C}\left(\frac{\operatorname{lcm}(i,j)}{\gcd(j,k)}\right)^{f(type)}
$$
其中 $f(type)$ 的取值如下：
$$
f(type) = \begin{cases} 1 &type = 0\\ i\times j\times k &type
= 1\\ \gcd(i,j,k) &type = 2 \end{cases}
$$
##### 分析
显然，原式等于：
$$
\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\dfrac{i\times
j }{\gcd(i,j)\times \gcd(i,k)}\right)^{f(type)}
$$
发现每一项仅与两个变量有关，设：
$$
\begin{aligned} f_1(a,b,c) &=
\prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} i^{f(type)}\\
f_2(a,b,c) &= \prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c}
\gcd(i,j)^{f(type)} \end{aligned}
$$
发现 $\prod$ 可以随意交换，则原式等价于：
$$
\dfrac{f_1(a,b,c)\times f_1(b,a,c)}{f_2(a,b,c)\times
f_2(a,c,b)}
$$
考虑在 $type$ 取值不同时，如何快速求得 $f_1$ 与 $f_2$。
##### $\large{type=0}
\begin{aligned} f_1(a,b,c) &=
\prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} i\\ f_2(a,b,c)
&= \prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} \gcd(i,j)
\end{aligned}
对于 f_1，显然有：
\prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} i =
\left(\prod_{i=1}^{a}i\right)^{b\times c}
预处理阶乘 + 快速幂即可，单次计算时间复杂度 O(\log n)。
再考虑 f_2，显然有：
\large \begin{aligned}
&\prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} \gcd(i,j)\\
=&\left(\prod_{i=1}^{a}\prod_{j=1}^{b}\gcd(i,j)\right)^c\\
=& \left(\prod_{d=1}
d^{\left(\sum\limits_{i=1}^{a}\sum\limits_{j=1}^{b}[\gcd(i,j)
= d]\right)}\right)^c \end{aligned}
先看指数，有：
\begin{aligned}
&\sum\limits_{i=1}^{a}\sum\limits_{j=1}^{b}[\gcd(i,j) =
d]\\ =&
\sum\limits_{i=1}^{\left\lfloor\frac{a}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{b}{d}\right\rfloor}[\gcd(i,j)
= 1]\\ =&
\sum\limits_{i=1}^{\left\lfloor\frac{a}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{b}{d}\right\rfloor}\sum_{k\mid
\gcd(i,j)}\mu (k)\\ =&
\sum_{k=1}\mu(k)\left\lfloor\dfrac{a}{kd}\right\rfloor\left\lfloor\dfrac{b}{kd}\right\rfloor
\end{aligned}
则原式等于：
\large \begin{aligned} &\left(\prod_{d=1}
d^{\left(\sum\limits_{k=1}\mu(k)\left\lfloor\frac{a}{kd}\right\rfloor\left\lfloor\frac{b}{kd}\right\rfloor\right)}\right)^c\\
=& \left(\prod_{d=1}
\left(d^{\sum\limits_{k=1}\mu(k)}\right)^{\left\lfloor\frac{a}{kd}\right\rfloor\left\lfloor\frac{b}{kd}\right\rfloor}\right)^c\\
=& \prod_{d=1}
\left(\prod_{k=1}^{\left\lfloor\frac{n}{d}\right\rfloor}d^{\left(\mu(k)\left\lfloor\frac{a}{kd}\right\rfloor\left\lfloor\frac{b}{kd}\right\rfloor\right)}\right)^c
\end{aligned}
设 t=kd，并枚举 t，有：
\large \prod_{t=1}^{n}\left(\left(\prod_{d|t}
d^{\mu{\left(\frac{t}{d}\right)}}\right)^{\left\lfloor\frac{a}{t}\right\rfloor\left\lfloor\frac{b}{t}\right\rfloor}\right)^c
显然，\prod\limits_{d|t}d^{\mu\left(\frac{t}{d}\right)} 这块可以预处理。
复杂度 O(n\log n)。
数论分块 \text{+} 快速幂计算即可，单次时间复杂度 O(\sqrt n\log
n)。
\large{type=1}
\begin{aligned} f_1(a,b,c) &=
\prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} i^{i\times
j\times k}\\ f_2(a,b,c) &=
\prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c}
\gcd(i,j)^{i\times j\times k} \end{aligned}
先考虑 f_1，有：
\large \prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c}
i^{i\times j\times k} =
\prod_{i=1}^{a}\prod_{j=1}^{b}i^{\left(i\times j\times
\sum\limits_{k = 1}^{c} k\right)}=
\left(\prod_{i=1}^{a}i^i\right)^{\operatorname{S}(b)\times \operatorname{S}(c)}
其中 \operatorname{S}(n)=\sum\limits_{i=1}^{n}=\frac{n\times (n+1)}{2}，可算 O(1) 算前缀和然后再用扩展欧拉定理降幂即可。
再考虑 f_2，显然有：
\large \begin{aligned}
&\prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} \gcd(i,j)^{i\times j\times k}\\
=& \left(\prod_{i=1}^a\prod_{j=1}^b\gcd(i,j)^{i\times j}\right)^{\operatorname{S}(c)}
\end{aligned}
然后枚举 gcd，原式等于：
\large \left(\prod_{d=1}d^{\left(\sum\limits_{i=1}^a \sum\limits_{j=1}^b i\times j[\gcd(i,j)=d]\right)}\right)^{\operatorname{S}(c)}
先看指数，有：
\large \begin{aligned}
&\sum\limits_{i=1}^a \sum\limits_{j=1}^b i\times j[\gcd(i,j)=d]\\
=& d^2 \sum\limits_{i=1}^{\left\lfloor\frac{a}{d}\right\rfloor} \sum\limits_{j=1}^{\left\lfloor\frac{b}{d}\right\rfloor} i\times j[\gcd(i,j)=1\\
=& d^2 \sum\limits_{i=1}^{\left\lfloor\frac{a}{d}\right\rfloor} i \sum\limits_{j=1}^{\left\lfloor\frac{b}{d}\right\rfloor} j\sum\limits_{t|\gcd(i,j)}\mu(t)\\
=& d^2 \sum\limits_{i=1}^{\left\lfloor\frac{a}{d}\right\rfloor} i \sum\limits_{j=1}^{\left\lfloor\frac{b}{d}\right\rfloor} j\sum\limits_{k|\gcd(i,j)}\mu(k)\\
=& d^2 \sum\limits_{k=1}\mu(k)\sum\limits_{i=1}^{\left\lfloor\frac{a}{d}\right\rfloor} i[k|i] \sum\limits_{j=1}^{\left\lfloor\frac{b}{d}\right\rfloor} j[k|j]\\
=& d^2 \sum\limits_{k=1}k^2\mu(k)\sum\limits_{i=1}^{\left\lfloor\frac{a}{kd}\right\rfloor} i\sum\limits_{j=1}^{\left\lfloor\frac{b}{kd}\right\rfloor} j\\
=& d^2\sum\limits_{k=1}k^2\mu(k)\operatorname{S}{\left(\left\lfloor\frac{a}{kd}\right\rfloor\right)} \operatorname{S}{\left(\left\lfloor\frac{b}{kd}\right\rfloor\right)}\\
\end{aligned}
则原式等于：
\large \left(\prod_{d=1}d^{\left(d^2\sum\limits_{k=1}k^2\mu(k)\operatorname{S}{\left(\left\lfloor\frac{a}{kd}\right\rfloor\right)} \operatorname{S}{\left(\left\lfloor\frac{b}{kd}\right\rfloor\right)}\right)}\right)^{\operatorname{S}(c)}
设 t=kd，并枚举 t，有：
\large \begin{aligned}
&\left(\prod_{d=1}\left(\prod_{k=1}^{\left\lfloor\frac{n}{d}\right\rfloor}d^{\left(d^2 k^2\mu(k)\right)}\right)^{\left(\operatorname{S}{\left(\left\lfloor\frac{a}{kd}\right\rfloor\right)} \operatorname{S}{\left(\left\lfloor\frac{b}{kd}\right\rfloor\right)}\right)}\right)^{\operatorname{S}(c)}\\
=& \prod_{t=1}\left(\left(\prod_{d|t}d^{\left(d^2\left(\frac{t}{d}\right)^2\mu\left(\frac{t}{d}\right)\right)}\right)^{\operatorname{S}{\left(\left\lfloor\frac{a}{t}\right\rfloor\right)} \operatorname{S}{\left(\left\lfloor\frac{b}{t}\right\rfloor\right)}}\right)^{\operatorname{S}(c)}\\
=& \prod_{t=1}\left(\left(\prod_{d|t}d^{\left(t^2\mu\left(\frac{t}{d}\right)\right)}\right)^{\operatorname{S}{\left(\left\lfloor\frac{a}{t}\right\rfloor\right)} \operatorname{S}{\left(\left\lfloor\frac{b}{t}\right\rfloor\right)}}\right)^{\operatorname{S}(c)}
\end{aligned}
显然，\prod\limits_{d|t}d^{\left(t^2\mu\left(\frac{t}{d}\right)\right)} 这块可以预处理。
复杂度 O(n\log^2 n)。
数论分块 \text{+} 快速幂计算即可，单次时间复杂度 O(\sqrt n\log
n)。
\large{type=2}
\begin{aligned} f_1(a,b,c) &=
\prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c}
i^{\gcd(i,j,k)}\\ f_2(a,b,c) &=
\prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c}
\gcd(i,j)^{\gcd(i,j,k)} \end{aligned}
直接考虑原式：
\prod_{i = 1}^a \prod_{j = 1}^b \prod_{k = 1}^c \left(\dfrac{\operatorname{lcm}(i, j)}{\gcd(i, k)} \right)^{\gcd(i, j, k)}
取 \ln 有：
\begin{aligned}
&\sum_{i = 1}^a \sum_{j = 1}^b \sum_{k = 1}^c \ln\left(\dfrac{\operatorname{lcm}(i, j)}{\gcd(i, k)} \right) \gcd(i, j, k)\\
& = \sum_{d = 1}^{\min(a, b, c)} \varphi(d) \sum_{i = 1}^{\left\lfloor\frac{a}{d}\right\rfloor} \sum_{j = 1}^{\left\lfloor\frac{b}{d}\right\rfloor} \sum_{k = 1}^{\left\lfloor\frac{c}{d}\right\rfloor} \ln\left(\dfrac{\operatorname{lcm}(id, jd)}{\gcd(id, kd)} \right) \\
& = \sum_{d = 1}^{\min(a, b, c)} \varphi(d) \sum_{i = 1}^{\left\lfloor\frac{a}{d}\right\rfloor} \sum_{j = 1}^{\left\lfloor\frac{b}{d}\right\rfloor} \sum_{k = 1}^{\left\lfloor\frac{c}{d}\right\rfloor} \ln\left(\dfrac{\operatorname{lcm}(i, j)}{\gcd(i, k)} \right)
\end{aligned}
取 \exp 有：
\prod_{d = 1}^{\min(a, b, c)} \left(\prod_{i = 1}^{\left\lfloor\frac{a}{d}\right\rfloor} \prod_{j = 1}^{\left\lfloor\frac{b}{d}\right\rfloor} \prod_{k = 1}^{\left\lfloor\frac{c}{d}\right\rfloor} \dfrac{\operatorname{lcm}(i, j)}{\gcd(i, k)} \right)^{\varphi(d)}
可以发现中间那部分其实就是 type=0 时的答案。
于是可以先对外层整除分块，再对内层整除分块。
CODE
P8570 [JRKSJ R6] 牵连的世界
link
番外
一些根号分治和优化除法。
参考资料
- oi-wiki 莫比乌斯反演
- [学习笔记] 莫比乌斯反演及杜教筛
- 总结与思考：数论分块
- oi-wiki 数论分块
- 铃悬的数学小讲堂——狄利克雷卷积与莫比乌斯反演
-
-
感谢 mango09 神仙的帮助。