浅谈莫反

题单

莫比乌斯反演

莫比乌斯反演是数论中很重要的内容。

对于一些函数 \(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 \]

其中 \(f\) 为某一个积性函数。

因为积性函数这个很好用的性质，所以我们可以直接对前半段的莫比乌斯函数维护一个前缀和，再利用整除分块处理式子的后半段，处理答案的时候，把两段相乘即可。

例题

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}^{n}(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=1\) 时为因数和函数，通常简记为 \(\sigma_{n}\)。
\(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\)
\(\epsilon\) 为狄利克雷卷积的单位元，有 \((f\ast \epsilon)(n) = f(n)\)。
若 \(f,g\) 为积性函数，则 \(f \ast g\) 为积性函数。
\(\epsilon = \mu \ast 1=\sum\limits_{d\mid n} \mu (d)\)。
\((\operatorname{Id}_k\ast 1)(n) = \sum_{d\mid n} \operatorname{Id_k}(d) = \sum_{d\mid n} d^k = \sigma_k(n)\)。
\(\begin{aligned} \varphi \ast 1 =& \operatorname{Id}\\ \varphi =& \operatorname{Id}\ast \mu \end{aligned}\)。

杜教筛

问题描述

求 \(S(n)=\sum\limits_{i=1}^{n}f(i)\)，其中 \(f(i)\) 为积性函数。

\(1\le n\le2^{31}\)。

算法解决

显然，线性筛是 \(\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\) 的前缀和就可以了。

什么叫快速算出 \(h\) 的前缀和呢？

比如说 \(\mu * I = \epsilon\) 的前缀和就非常的好算。

\(\varphi * I=id\) 的前缀和也非常的好算。

实战演练

\(\mu\) 的前缀和

因为 \(\mu * I=\epsilon\)，那么取 \(f=\mu,g=I,f*g=\epsilon\)。

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\)。

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; // 记忆化
}

莫比乌斯函数

定义

\(\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\) 函数为积性函数，因此可以线性筛莫比乌斯函数。

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_{d|n}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

求：

\[\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

SP26017 GCDMAT - GCD OF MATRIX

求：

\[\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

P3327 [SDOI2015]约数个数和

求：

\[\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_{j=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

P5221 Product

求：

\[\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

P6055 [RC-02] GCD

求：

\[\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,j)=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

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

[CQOI2015]选数

求：

\[\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

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

P1829 国家集训队Crash的数字表格 / JZPTAB

求（对 \(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

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) \]

预处理即可。

修改一下可过加强版。

P6156 简单题 CODE

P6222 「P6156 简单题」加强版 CODE

P6384 『MdOI R2』Quo Vadis

给定一个 无限大 的矩阵 \(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

P3704 [SDOI2017]数字表格

求：

\[\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

SP26045 GCDMAT2 - GCD OF MATRIX (hard)

~~最优解，嘿嘿。~~

求：

\[\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

循环之美

求 \(\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

P3700 [CQOI2017]小Q的表格

有一个表格，满足：

\[\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

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}{l},\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

P5572 [CmdOI2019]简单的数论题

求：

\[\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 毒瘤之神的考验差不多，将答案表示为关于 \(H\) 的差分加下取整的形式。

再考虑根号分治，我们设一个阈值，将所有范围内的 \(H\) 值递推预处理出来。

后面的再数论分块算。

CODE

P5518 [MtOI2019]幽灵乐团 / 莫比乌斯反演基础练习题

求：

\[\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} \]

对于 \(f_1\)，显然有：

\[\large \begin{aligned} &\prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} i^{\gcd(i,j,k)}\\ =&\prod_{d=1}\prod\limits_{i=1}^{a}i^{\left(\sum\limits_{j=1}^{b}\sum\limits_{k=1}^{c}[\gcd(i,j,k)=d]\right)}\\ =& \prod_{d=1}\prod\limits_{i=1}^{a}i^{\left(\sum\limits_{j=1}^{\left\lfloor\frac{b}{d}\right\rfloor}\sum\limits_{k=1}^{\left\lfloor\frac{c}{d}\right\rfloor}[\gcd(\frac{i}{d},j,k)=1]\right)}\\ =& \prod_{d=1}\prod\limits_{i=1}^{\left\lfloor\frac{a}{d}\right\rfloor}(id)^{\left(d\sum\limits_{j=1}^{\left\lfloor\frac{b}{d}\right\rfloor}\sum\limits_{k=1}^{\left\lfloor\frac{c}{d}\right\rfloor}[\gcd(i,j,k)=1]\right)}\\ =& \prod_{d=1}\prod\limits_{i=1}^{\left\lfloor\frac{a}{d}\right\rfloor}(id)^{\left(d\sum\limits_{j=1}^{\left\lfloor\frac{b}{d}\right\rfloor}\sum\limits_{k=1}^{\left\lfloor\frac{c}{d}\right\rfloor}\sum\limits_{x|\gcd(i,j,k)}{\mu(x)}\right)}\\ =& \prod_{d=1}\prod\limits_{i=1}^{\left\lfloor\frac{a}{d}\right\rfloor}(id)^{\left(d\sum\limits_{x=1}\mu(x)[x|i]\sum\limits_{j=1}^{\left\lfloor\frac{b}{d}\right\rfloor}[x|j]\sum\limits_{k=1}^{\left\lfloor\frac{c}{d}\right\rfloor}[x|k]\right)}\\ =& \prod_{d=1}\prod_{x=1}\prod\limits_{i=1}^{\left\lfloor\frac{a}{d}\right\rfloor}(id)^{\left(d\times \mu(x)[x|i]\sum\limits_{j=1}^{\left\lfloor\frac{b}{d}\right\rfloor}[x|j]\sum\limits_{k=1}^{\left\lfloor\frac{c}{d}\right\rfloor}[x|k]\right)}\\ =& \prod_{d=1}\prod_{x=1}\prod\limits_{i=1}^{\left\lfloor\frac{a}{xd}\right\rfloor}(ixd)^{\left(d\times \mu(x){\left\lfloor\frac{b}{xd}\right\rfloor}{\left\lfloor\frac{c}{xd}\right\rfloor}\right)}\\ =& \prod_{t = 1}\prod_{d|T}\prod_{i=1}^{\left\lfloor\frac{a}{t}\right\rfloor}(it)^{\left(d\times \mu\left(\frac{t}{d}\right){\left\lfloor\frac{b}{t}\right\rfloor}{\left\lfloor\frac{c}{t}\right\rfloor}\right)}\\ =& \prod_{t = 1}\prod_{d|T}\left(t^{\left\lfloor\frac{a}{t}\right\rfloor}\prod_{i=1}^{\left\lfloor\frac{a}{t}\right\rfloor}i\right)^{d\times \mu\left(\frac{t}{d}\right){\left\lfloor\frac{b}{t}\right\rfloor}{\left\lfloor\frac{c}{t}\right\rfloor}}\\ =&\prod_{t = 1}\prod_{d|t}\left(t^{\left\lfloor\frac{a}{t}\right\rfloor}\times \operatorname{fac}\left(\left\lfloor\frac{a}{t}\right\rfloor\right)\right)^{\left(d\times \mu\left(\frac{t}{d}\right){\left\lfloor\frac{b}{t}\right\rfloor}{\left\lfloor\frac{c}{t}\right\rfloor}\right)}& \operatorname{fac}(n)=\prod_{i=1}^{n}i\\ =& \prod_{t = 1}\left(\prod_{d|t}\left(t^{\left\lfloor\frac{a}{t}\right\rfloor}\times \operatorname{fac}\left(\left\lfloor\frac{a}{t}\right\rfloor\right)\right)^{d\times \mu\left(\frac{t}{d}\right)}\right)^{{\left\lfloor\frac{b}{t}\right\rfloor}{\left\lfloor\frac{c}{t}\right\rfloor}}\\ =& \prod_{t = 1}\left(\left(t^{\left\lfloor\frac{a}{t}\right\rfloor}\times \operatorname{fac}\left(\left\lfloor\frac{a}{t}\right\rfloor\right)\right)^{\sum\limits_{d|t}d\times \mu\left(\frac{t}{d}\right)}\right)^{{\left\lfloor\frac{b}{t}\right\rfloor}{\left\lfloor\frac{c}{t}\right\rfloor}}\\ =&\prod_{t = 1}\left(t^{\left\lfloor\frac{a}{t}\right\rfloor}\times \operatorname{fac}\left(\left\lfloor\frac{a}{t}\right\rfloor\right)\right)^{\varphi(t){\left\lfloor\frac{b}{t}\right\rfloor}{\left\lfloor\frac{c}{t}\right\rfloor}}\\ =& \prod_{t = 1}\left(t^{\varphi(t)\left\lfloor\frac{a}{t}\right\rfloor{\left\lfloor\frac{b}{t}\right\rfloor}{\left\lfloor\frac{c}{t}\right\rfloor}}\times \operatorname{fac}\left(\left\lfloor\frac{a}{t}\right\rfloor\right)^{\varphi(t){\left\lfloor\frac{b}{t}\right\rfloor}{\left\lfloor\frac{c}{t}\right\rfloor}}\right) \end{aligned} \]

预处理 \(t^{\varphi(t)}\) 的前缀积及逆元，阶乘的前缀积及阶乘逆元。

数论分块 \(\text{+}\) 快速幂计算即可，单次时间复杂度 \(O(\sqrt n\log n)\)。

再考虑 \(f_2\)，有：

\[\large \begin{aligned} &\prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} \gcd(i,j)^{\gcd(i,j,k)}\\ =& \prod_{d=1}\prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} [\gcd(i,j)=d] d^{\gcd(d,k)}\\ =& \prod_{d=1} \left(d^{\left(\sum\limits_{i=1}^{a}\sum\limits_{j=1}^{b} [\gcd(i,j)=d]\right)}\right)^{\sum\limits_{k=1}^{c}\gcd(d,k)} \end{aligned} \]

根据狄利克雷卷积 \(id=\varphi \ast 1\)，显然有：

\[\large \begin{aligned} &\sum\limits_{k=1}^{c}\gcd(d,k)\\ =& \sum\limits_{k=1}^{c}\sum_{x|\gcd(d,k)}\varphi(x)\\ =& \sum_{x=1}\varphi(x)[x|d]\sum_{k=1}^{c}[x|k]\\ =& \sum_{x|d}\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor \end{aligned} \]

根据之前推过的式子：

\[\sum\limits_{i=1}^{a}\sum\limits_{j=1}^{b}[\gcd(i,j) = d]=\sum_{y=1}\mu(y)\left\lfloor\dfrac{a}{yd}\right\rfloor\left\lfloor\dfrac{b}{yd}\right\rfloor \]

那么原式等于：

\[\large \begin{aligned} &\prod_{d=1} \left(d^{\left(\sum\limits_{y=1}\mu(y)\left\lfloor\frac{a}{yd}\right\rfloor\left\lfloor\frac{b}{yd}\right\rfloor\right)}\right)^{\sum\limits_{x|d}\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor}\\ =& \prod_{d=1} \left(\prod\limits_{y=1}d^{\left(\mu(y)\left\lfloor\frac{a}{yd}\right\rfloor\left\lfloor\frac{b}{yd}\right\rfloor\right)}\right)^{\sum\limits_{x|d}\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor} \end{aligned} \]

设 \(t=yd\)，并枚举 \(t\)，有：

\[\large \begin{aligned} &\prod_{d=1} \left(\prod\limits_{y=1}d^{\left(\mu(y)\left\lfloor\frac{a}{yd}\right\rfloor\left\lfloor\frac{b}{yd}\right\rfloor\right)}\right)^{\sum\limits_{x|d}\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor}\\ =& \prod_{t=1}\prod_{d|t} d^{\left(\mu\left(\frac{t}{d}\right)\left\lfloor\frac{a}{t}\right\rfloor\left\lfloor\frac{b}{t}\right\rfloor\sum\limits_{x|d}\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\right)}\\ =& \prod_{t=1}\left(\prod_{d|t} d^{\left(\mu\left(\frac{t}{d}\right)\sum\limits_{x|d}\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\right)}\right)^{\left\lfloor\frac{a}{t}\right\rfloor\left\lfloor\frac{b}{t}\right\rfloor}\\ =& \prod_{t=1}\left(\prod_{d|t} \prod_{x|d}d^{\left(\mu\left(\frac{t}{d}\right)\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\right)}\right)^{\left\lfloor\frac{a}{t}\right\rfloor\left\lfloor\frac{b}{t}\right\rfloor} \end{aligned} \]

考虑把 \(d\) 拆成 \(x\) 和 \(\frac{d}{x}\)。

分别计算贡献再相乘，即分别计算下两式：

\[\large \begin{aligned} &\prod_{t=1}\left(\prod_{d|t} \prod_{x|d}x^{\left(\mu\left(\frac{t}{d}\right)\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\right)}\right)^{\left\lfloor\frac{a}{t}\right\rfloor\left\lfloor\frac{b}{t}\right\rfloor}\\ &\prod_{t=1}\left(\prod_{d|t} \prod_{x|d}{\left(\frac{d}{x}\right)}^{\left(\mu\left(\frac{t}{d}\right)\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\right)}\right)^{\left\lfloor\frac{a}{t}\right\rfloor\left\lfloor\frac{b}{t}\right\rfloor} \end{aligned} \]

先考虑 \(x\) 的情况，首先把枚举 \(x\) 整到最外层。

设 \(\operatorname{lim}=\max(a,b,c)\)，则原式等于：

\[\large \begin{aligned} &\prod_{x=1} \prod_{t=1}^{\operatorname{lim}}[x|t]\left(\prod_{d|t} [x|d]{x}^{\left(\mu\left(\frac{t}{d}\right)\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\right)}\right)^{\left\lfloor\frac{a}{t}\right\rfloor\left\lfloor\frac{b}{t}\right\rfloor}\\ =& \prod_{x=1} \prod_{t=1}^{\left\lfloor\frac{\operatorname{lim}}{x}\right\rfloor}\left(\prod_{d|t} {x}^{\left(\mu\left(\frac{tx}{dx}\right)\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\right)}\right)^{\left\lfloor\frac{a}{tx}\right\rfloor\left\lfloor\frac{b}{tx}\right\rfloor}\\ =& \prod_{x=1} \prod_{t=1}^{\left\lfloor\frac{\operatorname{lim}}{x}\right\rfloor}\prod_{d|t} {x}^{\left(\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\left\lfloor\frac{a}{tx}\right\rfloor\left\lfloor\frac{b}{tx}\right\rfloor\mu\left(\frac{t}{d}\right)\right)}\\ =&\prod_{x=1} {x}^{\left(\sum\limits_{t=1}^{\left\lfloor\frac{\operatorname{lim}}{x}\right\rfloor}\sum\limits_{d|t}\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\left\lfloor\frac{a}{tx}\right\rfloor\left\lfloor\frac{b}{tx}\right\rfloor\mu\left(\frac{t}{d}\right)\right)}\\ =& \prod_{x=1} {x}^{\left(\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\sum\limits_{t=1}^{\left\lfloor\frac{\operatorname{lim}}{x}\right\rfloor}\left\lfloor\frac{a}{tx}\right\rfloor\left\lfloor\frac{b}{tx}\right\rfloor\sum\limits_{d|t}\mu\left(\frac{t}{d}\right)\right)} \end{aligned} \]

根据狄利克雷卷积 \((\mu \ast 1) (n)= \epsilon (n)=[n=1]\)，显然有：

\[\large \begin{aligned} &\prod_{x=1} {x}^{\left(\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\sum\limits_{t=1}^{\left\lfloor\frac{\operatorname{lim}}{x}\right\rfloor}\left\lfloor\frac{a}{tx}\right\rfloor\left\lfloor\frac{b}{tx}\right\rfloor[t=1]\right)}\\ =& \prod_{x=1} {x}^{\left(\varphi(x)\left\lfloor\frac{a}{x}\right\rfloor\left\lfloor\frac{b}{x}\right\rfloor\left\lfloor\frac{c}{x}\right\rfloor\right)} \end{aligned} \]

直接整除分块即可。

再考虑 \(\frac{d}{x}\) 的情况，同上先把枚举 \(x\) 放到最外层，并调整一下指数，则原式等于：

\[\large \begin{aligned} &\prod_{x=1} \prod_{t=1}^{\operatorname{lim}}[x|t]\left(\prod_{d|t} [x|d]{\left(\frac{d}{x}\right)}^{\left(\mu\left(\frac{t}{d}\right)\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\right)}\right)^{\left\lfloor\frac{a}{t}\right\rfloor\left\lfloor\frac{b}{t}\right\rfloor}\\ =& \prod_{x=1} \prod_{t=1}^{\left\lfloor\frac{\operatorname{lim}}{x}\right\rfloor}\left(\prod_{d|tx} [x|d]{\left(\frac{d}{x}\right)}^{\left(\mu\left(\frac{tx}{d}\right)\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\right)}\right)^{\left\lfloor\frac{a}{tx}\right\rfloor\left\lfloor\frac{b}{tx}\right\rfloor}\\ =& \prod_{x=1} \left(\prod_{t=1}^{\left\lfloor\frac{\operatorname{lim}}{x}\right\rfloor}\left(\prod_{d|tx} [x|d]{\left(\frac{d}{x}\right)}^{\mu\left(\frac{tx}{d}\right)}\right)^{\left\lfloor\frac{a}{tx}\right\rfloor\left\lfloor\frac{b}{tx}\right\rfloor}\right)^{\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor} \end{aligned} \]

考虑枚举 \(dx\)，替换原来的 \(d\)，则原式等于：

\[\large \begin{aligned}&\prod_{x=1} \left(\prod_{t=1}^{\left\lfloor\frac{\operatorname{lim}}{x}\right\rfloor}\left(\prod_{d|t}d^{\mu\left(\frac{t}{d}\right)}\right)^{\left\lfloor\frac{a}{tx}\right\rfloor\left\lfloor\frac{b}{tx}\right\rfloor}\right)^{\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor}\\ =& \prod_{x=1} \left(\prod_{t=1}^{\left\lfloor\frac{\operatorname{lim}}{x}\right\rfloor}\left(\prod_{d|t}d^{\mu\left(\frac{t}{d}\right)}\right)^{\left\lfloor\frac{\left\lfloor\frac{a}{x}\right\rfloor}{t}\right\rfloor\left\lfloor\frac{\left\lfloor\frac{b}{x}\right\rfloor}{t}\right\rfloor}\right)^{\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor} \end{aligned} \]

其中 \(\left(\prod\limits_{d|t}d^{\mu\left(\frac{t}{d}\right)}\right)\) 预处理即可。

于是可以先对外层整除分块，再对内层整除分块。

然后就做完了，没了。

CODE

参考资料

oi-wiki 莫比乌斯反演
[学习笔记] 莫比乌斯反演及杜教筛
总结与思考：数论分块
oi-wiki 数论分块
铃悬的数学小讲堂——狄利克雷卷积与莫比乌斯反演

浅谈莫反

莫比乌斯反演

前置知识

艾佛森括号

数论分块

引理

形式一

形式二

形式三

例题

P3935 Calculating

P2260 [清华集训2012]模积和

积性函数

定义

性质

常见积性函数

狄利克雷卷积

定义

性质

杜教筛

问题描述

算法解决

实战演练

\(\mu\) 的前缀和

\(\varphi\) 的前缀和

莫比乌斯函数

定义

性质

结论

莫比乌斯变换

形式一

形式二

常见的几种反演形式

形式一

形式二

形式三

例题

SP4491 PGCD - Primes in GCD Table

SP26017 GCDMAT - GCD OF MATRIX

P3327 [SDOI2015]约数个数和

P5221 Product

P6055 [RC-02] GCD

P3768 简单的数学题

[CQOI2015]选数

P4449 于神之怒加强版

P1829 国家集训队Crash的数字表格 / JZPTAB

P6156 简单题

P6384 『MdOI R2』Quo Vadis

P3704 [SDOI2017]数字表格

SP26045 GCDMAT2 - GCD OF MATRIX (hard)

循环之美

P3700 [CQOI2017]小Q的表格

P4240 毒瘤之神的考验

P5572 [CmdOI2019]简单的数论题

P5518 [MtOI2019]幽灵乐团 / 莫比乌斯反演基础练习题

分析

\(\large{type=0}\)

\(\large{type=1}\)

\(\large{type=2}\)

参考资料

相关

标签