莫比乌斯反演

数论函数

数论函数： 定义域为正整数的函数。

积性函数： 对于任意两个互质的正整数 $a, b$，均满足 $f(ab)=f(a)\times f(b)$ 的函数 $f$

完全积性函数： 对于所有正整数 $a, b$，均满足 $f
(ab)=f(a)\times f(b)$ 的函数 $f$

对于一个积性函数 $f$，$f(n)=f(\prod p_i^{a_i})=\prod f(p_i^{a_i})$，若 $f$ 还满足完全积性，则 $f(n)=\prod f(p_i)^{a_i}$

常见积性函数

欧拉函数 $\varphi(n)$

莫比乌斯函数 $\mu(n)$： 若 $n$ 有平方数因子，则 $\mu(n)=0$。否则若 $n$ 为 $k$ 个不同质数之积，则 $\mu(n)=(-1)^k$。

$$\mu(n)= \begin{cases} 1 & n=1\\ (-1)^k & n=p_1p_2\cdots p_k\\ 0 & \text{else} \end{cases}$$

除数函数： $\sigma_k(n)$ 表示 $n$ 的所有正因子的 $k$ 次幂之和。

$d(n)=\sigma_0(n)$ 表示 $n$ 的正因子个数，$\sigma(n)=\sigma_1(n)$ 表示 $n$ 的所有正因子之和。

幂函数： $\operatorname{Id}_k(n)=n^k$，$1(n)=\operatorname{Id}_0(n)=1$，$\operatorname{Id}(n)=\operatorname{Id}_1(n)=n$

单位函数：
$e(n)=\varepsilon(n)=
\begin{cases}
1 & n = 1\\
0 & n > 1
\end{cases}
$

狄利克雷（Dirichlet）卷积

定义两个数论函数 $f$，$g$ 的 Dirichlet 卷积：

$$(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})$$

狄利克雷卷积的性质

交换律：

$$f*g=g*f$$

结合律：

$$(f*g)*h=f*(g*h)$$

分配律：

$$f*(g+h)=f*g+f*h$$

单位元：

$$f*\varepsilon=\varepsilon*f$$

常见的狄利克雷卷积

• $d(n)=\sum_{d|n}1$，即 $d=1*1$

• $\sigma(n)=\sum_{d|n}d$，即 $\sigma=d*1$

• $\varphi(n)=\sum_{d|n}\mu(d)\frac{n}{d}$，即 $\varphi=\mu*\operatorname{Id}$

• $\varepsilon(n)=\sum_{d|n}\mu(d)$，即 $\varepsilon=\mu*1$

一些结论和证明

$n = \sum_{d|n}\varphi(d)$。

$1$ 到 $n$ 中与 $n(n>1)$ 互质的数的和为 $\dfrac{n\times \varphi(n)}{2}$。

$\varepsilon=\mu*1$ 即为 $\sum_{d|n}\mu(d)=[n=1]$。

证明：$n=1$ 时 $\sum_{d|n}\mu(d)=1$。

$n \neq 1$ 时，设 $n$ 有 $k$ 个质因子，只有当 $n$ 的因子中所有质因子次数都为 $1$ 时，$\mu$ 不为 $0$，即

$$\begin{aligned} \sum_{d|n}\mu(d) &=\sum_{i=0}^{k}(-1)^{i}C(k,i)\\ &= (1-1)^k\\ &=0 \end{aligned}$$

因此 $\sum_{d|n}\mu(d)=[n=1]$。

莫比乌斯反演

若两个函数 $f$，$g$ 满足：

$$f(n)=\sum_{d|n}g(d)$$

则它们也满足

$$g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d})$$

反之亦然，即

$$f=g*1\Leftrightarrow g=\mu *f$$

它的另一个形式：

$$f(n)=\sum_{n|d}g(d)\Leftrightarrow g(n)=\sum_{n|d}\mu(d)f(\frac{d}{n})$$

线性筛

反演的题目经常会需要快速求积性函数，这时就要用到线性筛。

线性筛质数

设 $pr_i$ 表示 $i$ 的最小质因子。枚举所有不超过 $pr_i$ 的质数 $p$，使 $pr_(i\cdot p) = p$，相当于将每个数的质因子降序分解，每个数只会被它的最小质因子筛一次，因此复杂度是 $O(n)$ 的。

void Shaker(int x)
{
    for (int i = 2; i <= x; i++)
    {
        if (!pr[i]) prime[++cnt] = pr[i] = i;
        for (int j = 1; j <= cnt; j++)
        {
			int k = i * prime[j];
			if (k > x) break;
            pr[k] = prime[j];
            if (i % prime[j] == 0) break;
        }
    }
}

线性筛积性函数

利用线性筛求解每个数 $n$ 的最小质因子 $p$ 的次数 $k$：令 $n = pm$，由于 $p$ 是 $n$ 最小的质因子，若 $p^2 | n$
，则 $p | m$ ，并且 $p$ 也是 $m$ 最小的质因子，这样在筛法的同时即可算出新筛去的合数的最小质因子的次数。

这样在求解积性函数时，我们能利用 $f(n)=f(p^k)f(\frac{n}{p^k})$，在线性筛的同时快速求出 $f(n)$。

线性筛欧拉函数

$\varphi(p^k)=(p-1)p^{k-1}$，因此筛法时，若 $p | m$，$\varphi$ 就乘上 $p$，否则乘上 $p-1$。

void Shaker(int x)
{
    phi[1] = 1;
    for (int i = 2; i <= x; i++)
    {
        if (!pr[i]) prime[++cnt] = pr[i] = i, phi[i] = i - 1;
        for (int j = 1; j <= cnt; j++)
        {
			int k = i * prime[j];
			if (k > x) break;
            pr[k] = prime[j];
            if (i % prime[j] == 0)
            {
                phi[k] = phi[i] * prime[j];
                break;
            }
            phi[k] = phi[i] * (prime[j] - 1);
        }
    }
}

线性筛莫比乌斯函数

只有当 $k=1$ 时 $\mu(p^k)=-1$，否则 $\mu(p^k)=0$。

void Shaker(int x)
{
    mu[1] = 1;
    for (int i = 2; i <= x; i++)
    {
        if (!pr[i]) prime[++cnt] = pr[i] = i, mu[i] = -1;
        for (int j = 1; j <= cnt; j++)
        {
			int k = i * prime[j];
			if (k > x) break;
            pr[k] = prime[j];
            if (i % prime[j] == 0)
            {
                mu[k] = 0;
                break;
            }
            mu[k] = -mu[i];
        }
    }
}

筛法求约数个数、约数和

约数个数 $d_i$ 是积性函数，因此也可以用筛法求。类似的可以求约数和、最小质因子 $k$ 次幂的和。

求约数个数。$num_i$ 表示 $i$ 的最小质因子出现次数。

void Shaker(int x)
{
    d[1] = 1;
    for (int i = 2; i <= x; i++)
    {
        if (!pr[i]) prime[++cnt] = pr[i] = i, d[i] = 2, num[i] = 1;
        for (int j = 1; j <= cnt; j++)
        {
			int k = i * prime[j];
			if (k > x) break;
            pr[k] = prime[j];
            if (i % prime[j] == 0)
            {
                num[k] = num[i] + 1;
                d[k] = d[i] / num[k] * (num[k] + 1);
                break;
            }
            num[k] = 1;
            d[k] = d[i] * 2;
        }
    }
}

求约数和。$f_i$ 表示 $i$ 的约数和，$g_i$ 表示 $i$ 的最小质因子的 $p^0+p^1+p^2+\cdots +p^k$.

void Shaker(int x)
{
    g[1] = f[1] = 1;
    for (int i = 2; i <= x; i++)
    {
        if (!pr[i]) prime[++cnt] = pr[i] = i, g[i] = f[i] = i + 1;
        for (int j = 1; j <= cnt; j++)
        {
			int k = i * prime[j];
			if (k > x) break;
            pr[k] = prime[j];
            if (i % prime[j] == 0)
            {
                g[k] = g[i] * prime[j] + 1;
                f[k] = f[i] / g[i] * g[k];
                break;
            }
            g[k] = prime[j] + 1;
            f[k] = f[i] * f[prime[j]];
        }
    }
}

题目

BZOJ 2705

求

$$F(n)=\sum_{i=1}^n \gcd(i,n)$$ $$\begin{aligned} F(n)&=\sum_{i=1}^n \gcd(i,n)\\ &= \sum_{i=1}^n \sum_{d}[d\ |\ \gcd(i,n)] \ \varphi(d)\\ &=\sum_{i=1}^n \sum_{d} [d\ |\ i][d\ | \ n]\ \varphi(d)\\ &=\sum_{d|n}\varphi(d)\sum_{i=1}^n [d\ |\ i]\\ &=\sum_{d|i}\varphi(d)\frac{n}{d} \end{aligned}$$

$F$ 是积性函数，因此直接 $O(\sqrt n)$ 质因数分解得到答案。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

LL n, ans = 1;

void Factor(LL x)
{
	for (LL i = 2; i * i <= x; i++)
	{
		if (x % i == 0)
		{
			LL p = i, k = 0, res = 1;
			while (x % i == 0) x /= i, k++, res *= p;
			ans *= res + k * (p - 1) * res / p;
		}
	}
	if (x > 1) ans *= x + (x - 1);
}

int main()
{
	cin >> n;
	Factor(n);
	cout << ans << endl;
	return 0;
}

BZOJ 2226

求

$$F(n)=\sum_{i=1}^n \text{lcm}(i,j)$$

令

$$G(n)=\sum_{i=1}^n [\gcd(n,i)=1]\ i$$ $$G(n)=\begin{cases} \frac{n\cdot \varphi(n)}{2}, &n>1\\ 1, &n=1 \end{cases}$$ $$\begin{aligned} F(n)&=\sum_{i=1}^n \text{lcm}(i,j)\\ &=\sum_{i=1}^n \frac{n\cdot i}{\gcd(n,i)}\\ &=\sum_{d|n} \sum_{i=1}^n [\gcd(n,i)=d] \ \frac{ni}{d}\\ &=\sum_{d|n} \sum_{i=1}^{\frac{n}{d}} [\gcd(\frac{n}{d},i)=1] \ ni\\ &=n\sum_{d|n}G(\frac{n}{d})\\ &=n\sum_{d|n}G(d)\\ &=\frac{n((\sum_{d|n}d\cdot \varphi(d))+1)}{2} \end{aligned}$$

$\sum_{d|n}d\cdot \varphi(d)$ 是积性函数，因此可以线性筛 $O(n)$ 预处理，单次询问 $O(1)$。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1000000 + 5;

int prime[N], pr[N], cnt;
LL f[N], g[N];

void Shaker(int x)
{
    f[1] = 1;
    for (int i = 2; i <= x; i++)
    {
        if (!pr[i])
        {
            prime[++cnt] = pr[i] = i;
            g[i] = i;
            f[i] = (i - 1) * g[i] + 1;
        }
        for (int j = 1; j <= cnt; j++)
        {
            int k = i * prime[j];
			if (k > x) break;
            pr[k] = prime[j];
            if (i % prime[j] == 0)
            {
                g[k] = g[i] * prime[j] * prime[j] + prime[j];
                f[k] = f[i] / ((prime[j] - 1) * g[i] + 1) * ((prime[j] - 1) * g[k] + 1);
                break;
            }
            g[k] = prime[j];
            f[k] = f[i] * ((prime[j] - 1) * g[k] + 1);
        }
    }
}

int main()
{
	Shaker(1000000);
	int T;
	scanf("%d", &T);
	while (T--)
	{
		LL n;
		scanf("%lld", &n);
		printf("%lld\n", n * (f[n] + 1) / 2);
	}
	return 0;
}

Luogu P1447

求

$$2\cdot \sum_{i=1}^n\sum_{j=1}^{m}\gcd(i,j)-n\cdot m$$ $$\begin{aligned} F(n)&=\sum_{i=1}^n\sum_{j=1}^{m}\gcd(i,j)\\ &=\sum_{i=1}^n\sum_{j=1}^m\sum_d [d\ |\ i][d\ |\ j]\ \varphi(d)\\ &=\sum_{d=1}^n \varphi(d)\cdot \lfloor \frac{n}{d}\rfloor \cdot \lfloor \frac{m}{d}\rfloor \end{aligned}$$

除法分块，$O(\sqrt n)$。

#include <bits/stdc++.h>
#define fl first
#define fr second
#define pb push_back
#define mp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
const int N = 100000 + 5;

LL sum[N];
int prime[N], pr[N], phi[N], cnt;

void Shaker(int x)
{
    phi[1] = 1;
    for (int i = 2; i <= x; i++)
    {
        if (!pr[i]) prime[++cnt] = pr[i] = i, phi[i] = i - 1;
        for (int j = 1; j <= cnt; j++)
        {
			int k = i * prime[j];
			if (k > x) break;
            pr[k] = prime[j];
            if (i % prime[j] == 0)
            {
                phi[k] = phi[i] * prime[j];
                break;
            }
            phi[k] = phi[i] * (prime[j] - 1);
        }
    }
    for (int i = 1; i <= x; i++) sum[i] = sum[i - 1] + phi[i];
}

inline LL F(LL n, LL m)
{
    LL res = 0;
    for (register LL l = 1, r; l <= min(n, m); l = r + 1)
    {
        r = min(n / (n / l), m / (m / l));
        res += (sum[r] - sum[l - 1]) * (n / l) * (m / l);
    }
    return res;
}

int main()
{
    Shaker(N - 5);
    int n, m;
    cin >> n >> m;
    cout << F(n, m) * 2 - 1LL * n * m << endl;
	return 0;
}

Luogu P1829

求

$$F(n,m)=\sum_{i=1}^n \sum_{j=1}^{m} \text{lcm}(i,j)$$ $$\begin{aligned} F(n,m)&=\sum_{i=1}^n \sum_{j=1}^{m} \text{lcm}(i,j)\\ &=\sum_{i=1}^n\sum_{j=1}^m \frac{i\cdot j}{\gcd(i,j)}\\ &=\sum_{i=1}^n\sum_{j=1}^m \sum_{d}[d\ |\ i][d\ |\ j]\ \frac{i\cdot j}{d}\ [\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}i \cdot j\ [\gcd(i,j)=1] \end{aligned}$$

我们令

$$G(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}i \cdot j\ [\gcd(i,j)=1]$$

有

$$\begin{aligned} G(n,m)&=\sum_{i=1}^n\sum_{j=1}^m i\cdot j\ [\gcd(i,j)=1]\\ &=\sum_{i=1}^n\sum_{j=1}^m i\cdot j\sum_{d}[d\ |\ i][d\ |\ j]\mu(d)\\ &=\sum_{d=1}^n\sum_{d|i}^n\sum_{d|j}^m \mu(d)\cdot i \cdot j\\ &=\sum_{d=1}^n\mu(d)\cdot d^2\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{d}\rfloor}i \cdot j\\ &=\sum_{d=1}^n \mu(d)\cdot d^2\cdot \frac{n(n+1)}{2}\cdot \frac{m(m+1)}{2} \end{aligned}$$

$G(n,m)$，$F(n,m)$ 都可以除法分块求，时间复杂度 $O(n)$。

#include <bits/stdc++.h>
#define fl first
#define fr second
#define pb push_back
#define mp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
const int N = 1e7 + 5;
const int mod = 20101009;

LL sum[N];
int prime[N], pr[N], mu[N], cnt;

inline LL ch(LL x)
{
    return (x % mod + mod) % mod;
}

void Shaker(int x)
{
    mu[1] = 1;
    for (int i = 2; i <= x; i++)
    {
        if (!pr[i]) prime[++cnt] = pr[i] = i, mu[i] = -1;
        for (int j = 1; j <= cnt; j++)
        {
			int k = i * prime[j];
			if (k > x) break;
            pr[k] = prime[j];
            if (i % prime[j] == 0)
            {
                mu[k] = 0;
                break;
            }
            mu[k] = -mu[i];
        }
    }
    for (int i = 1; i <= x; i++) sum[i] = ch(sum[i - 1] + 1LL * mu[i] * i * i % mod);
}

inline LL Sum(LL n)
{
    return ch(n * (n + 1) / 2 % mod);
}

inline LL G(LL n, LL m)
{
    LL res = 0;
    for (LL l = 1, r; l <= min(n, m); l = r + 1)
    {
        r = min(n / (n / l), m / (m / l));
        res = ch(res + ch(sum[r] - sum[l - 1] + mod) * Sum(n / l) % mod * Sum(m / l) % mod);
    }
    return res;
}

inline LL F(LL n, LL m)
{
    LL res = 0;
    for (LL l = 1, r; l <= min(n, m); l = r + 1)
    {
        r = min(n / (n / l), m / (m / l));
        res = ch(res + (r - l + 1) * (l + r) / 2 % mod * G(n / l, m / l) % mod);
    }
    return res;
}

int main()
{
    Shaker(10000000);
    LL n, m;
    cin >> n >> m;
    cout << F(n, m) << endl;
	return 0;
}

Luogu P2257

求

$$F(n)=\sum_{i=1}^n\sum_{j=1}^n [\gcd(i,j)\in primes]$$

方法一：这题主要难处理的是 $[\gcd(i,j)\in primes]$，如果我们有一个 $f$，使得 $\sum_{d|n}f(d)=[n\in primes]$ 就比较好了。 $f$ 容易用反演的套路 $O(n\log n)$ 递推出来。

方法二：

$$\begin{aligned} F(n)&=\sum_{i=1}^n\sum_{j=1}^n [\gcd(i,j)\in primes]\\ &=\sum_{p=1}^n [p\in primes]\sum_{i=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{p}\rfloor}[\gcd(i,j)=1]\\ &=\sum_{p=1}^n [p\in primes]\sum_{d=1}^n \mu(d)\lfloor \frac{n}{pd}\rfloor\lfloor \frac{m}{pd}\rfloor \end{aligned}$$

根据套路，我们枚举 $k=pd$，

$$\begin{aligned} F(n)&=\sum_{k=1}^n\sum_{p\in primes}\mu(\frac{k}{p})\lfloor \frac{n}{k}\rfloor\lfloor \frac{m}{k}\rfloor \end{aligned}$$

可以线性筛求出 $\mu$，然后 $O(n\log n)$ 枚举因数求出 $\sum_{p\in primes}\mu(\frac{k}{p})$ 的前缀和。

Luogu P3327

求

$$\sum_{i=1}^n \sum_{j=1}^m d(ij)$$

其中 $d(x)$ 表示 $x$ 的约数个数。

这题只需要知道

$$d(ij)=\sum_{x|i}\sum_{y|j}[\gcd(x,y)=1]$$

即可，剩下的都是套路了。

另外，还有一个与这相似的式子：

$$\sigma(ij)=\sum_{x\mid i}\sum_{y\mid j}x\cdot \frac{j}{y}[(x,y)=1]$$

原理与上面类似，都是对于每个质因子，它的幂在 $x$ 或 $y$ 上是 $0$，于是便能取到所有的幂。

杜教筛

原理

杜教筛可以处理数论函数前缀和问题。

对于数论函数 $f$，想要计算 $S(n)=\sum_{i=1}^nf(i)$。

对于任意一个数论函数 $g$，一定满足

$$\sum_{i=1}^{n}\sum_{d \mid i}f(d)g\left(\frac{i}{d}\right)=\sum_{i=1}^{n}g(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\ \Leftrightarrow \sum_{i=1}^{n}(f\ast g)(i)=\sum_{i=1}^{n}g(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$$

证明：

$$\begin{aligned} &\sum_{i=1}^n\sum_{d \mid i}f(d)g\left(\frac{i}{d}\right)\\ =&\sum_{i=1}^n\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}g(i)f(j)\\ =&\sum_{i=1}^ng(i)\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}f(j)\\ =&\sum_{i=1}^ng(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right) \end{aligned}$$

就是交换了下求和顺序，然后把枚举 $i$ 变成了枚举 $\frac{i}{d}$。

那么就可以得到递推式

$$g(1)S(n)=\sum_{i=1}^n(f\ast g)(i)-\sum_{i=2}^n g(i)S\left(\left\lfloor \frac{n}{i}\right\rfloor\right)$$

假如我们可以快速对 $\sum_{i=1}^n(f\ast g)(i)$ 求和，并用数论分块求解 $\sum_{i=2}^n g(i)S\left(\left\lfloor \frac{n}{i}\right\rfloor\right)$，就可以在较短时间内求得 $g(1)S(n)$。

莫比乌斯函数前缀和

我们知道，$\epsilon =\mu \ast 1$，即 $\epsilon(n)=\sum_{d \mid n} \mu(d)$。

因此，$S(n)=\sum_{i=1}^n \epsilon(i)-\sum_{i=2}^n S(\lfloor \frac{n}{i}\rfloor)=1-\sum_{i=2}^n S(\lfloor \frac{n}{i}\rfloor)$。

用线性筛预处理出前 $n^{\frac{2}{3}}$ 项，剩余部分用整除分块计算，总时间复杂度为 $O(n^{\frac{2}{3}})$。

欧拉函数前缀和

直接用莫比乌斯反演：

$$\sum_{i=1}^n \sum_{j=1}^n 1[\gcd(i,j)=1]=\sum_{i=1}^n \sum_{j=1}^n \sum_{d \mid i,d \mid j} \mu(d)$$

对于 $\sum_{i=1}^n \sum_{j=1}^i 1[\gcd(i,j)=1]$，排除掉 $i=1,j=1$ 的情况，再将结果除以 $2$ 即可。

当然也可以用杜教筛，$\varphi\ast 1=ID$

$$\begin{aligned} &\sum_{i=1}^n(\varphi\ast 1)(i)=\sum_{i=1}^n1\cdot S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\ &\sum_{i=1}^nID(i)=\sum_{i=1}^n1\cdot S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\ &\frac{1}{2}n(n+1)=\sum_{i=1}^nS\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\ &S(n)=\frac{1}{2}n(n+1)-\sum_{i=2}^nS\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\ \end{aligned}$$

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
const int N = 2000000 + 5;

int prime[N], pr[N], mu[N], sum[N], cnt;
map<LL, LL> Mu;

void Shaker(int x)
{
    mu[1] = 1;
    for (int i = 2; i <= x; i++)
    {
        if (!pr[i]) prime[++cnt] = pr[i] = i, mu[i] = -1;
        for (int j = 1; j <= cnt; j++)
        {
			int k = i * prime[j];
			if (k > x) break;
            pr[k] = prime[j];
            if (i % prime[j] == 0)
            {
                mu[k] = 0;
                break;
            }
            mu[k] = -mu[i];
        }
    }
    for (int i = 1; i <= x; i++) sum[i] = sum[i - 1] + mu[i];
}

LL Get_mu(LL x)
{
    if (x <= N - 5) return sum[x];
    if (Mu[x]) return Mu[x];
    LL res = 1;
    for (LL i = 2, j; i <= x; i = j + 1)
    {
        j = x / (x / i);
        res -= Get_mu(x / i) * (j - i + 1);
    }
    return Mu[x] = res;
}

LL Get_phi(LL x)
{
    LL res = 0;
    for (LL i = 1, j; i <= x; i = j + 1)
    {
        j = x / (x / i);
        res += (Get_mu(j) - Get_mu(i - 1)) * (x / i) * (x / i);
    }
    return (res - 1) / 2 + 1;
}

int main()
{
    Shaker(N - 5);
    int T;
    scanf("%d", &T);
    while (T--)
    {
        LL n;
        scanf("%lld", &n);
        printf("%lld %lld\n", Get_phi(n), Get_mu(n));
    }
    return 0;
}

P3768 简单的数学题

求

$$\sum_{i=1}^n\sum_{j=1}^ni\cdot j\cdot\gcd(i,j)\pmod p$$

先将其化为

$$\sum_{d=1}^nF^2\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\cdot d^2\varphi(d) \left(F(n)=\frac{1}{2}n\left(n+1\right)\right)\\$$

现在我们想求 $f(n)=n^2\varphi(n)$ 的前缀和，于是我们尝试构造 $g$，使 $f\ast g$ 和 $g$ 能够快速求和。

给 $f$ 卷上 $ID^2$，化简一下，得到

$$\begin{aligned} &(ID^2\varphi)\ast ID^2)(i)\\ =&\sum_{d \mid i}(ID^2\varphi)(d)ID^2\left(\frac{i}{d}\right)\\ =&\sum_{d \mid i}d^2\varphi(d)\left(\frac{i}{d}\right)^2\\ =&\sum_{d \mid i}i^2\varphi(d)=i^2\sum_{d \mid i}\varphi(d)\\ =&i^2(\varphi\ast1)(i)=i^3 \end{aligned}$$

再化一下 $S(n)$

$$\begin{aligned} S(n)&=\sum_{i=1}^n\left((ID^2\varphi)\ast ID^2\right)(i)-\sum_{i=2}^nID^2(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\ &=\sum_{i=1}^ni^3-\sum_{i=2}^ni^2S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\ &=\left(\frac{1}{2}n(n+1)\right)^2-\sum_{i=2}^ni^2S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\ \end{aligned}$$

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
const int N = 5e6 + 5;

int prime[N], phi[N], cnt;
LL sum[N], n, p, inv2, inv6;
unordered_map<LL, LL> Map;
bool pr[N];

void Shaker(int x)
{
    phi[1] = 1;
    for (int i = 2; i <= x; i++)
    {
        if (!pr[i]) prime[++cnt] = i, pr[i] = 1, phi[i] = i - 1;
        for (int j = 1; j <= cnt; j++)
        {
			int k = i * prime[j];
			if (k > x) break;
            pr[k] = 1;
            if (i % prime[j] == 0)
            {
                phi[k] = phi[i] * prime[j];
                break;
            }
            phi[k] = phi[i] * (prime[j] - 1);
        }
    }
    for (int i = 1; i <= x; i++) sum[i] = (sum[i - 1] + 1LL * i * i % p * phi[i]) % p;
}

LL qpow(LL a, LL b)
{
    LL res = 1;
    for (; b; b >>= 1, a = a * a % p)
        if (b & 1) res = res * a % p;
    return res;
}

LL Inv(LL x)
{
    return qpow(x, p - 2);
}

LL Get_Sum2(LL x)
{
    x %= p;
    return x * (x + 1) % p * (x * 2 + 1) % p * inv6 % p;
}

LL Get_Sum3(LL x)
{
    x %= p;
    return x * (x + 1) % p * inv2 % p * x % p * (x + 1) % p * inv2 % p;
}

LL S(LL x)
{
    if (x <= N - 5) return sum[x];
    if (Map[x]) return Map[x];
    LL res = Get_Sum3(x);
    for (LL l = 2, r; l <= x; l = r + 1)
    {
        r = x / (x / l);
        res = (res - (Get_Sum2(r) - Get_Sum2(l - 1)) % p * S(x / l)) % p;
    }
    return Map[x] = (res + p) % p;
}

LL Solve(LL x)
{
    LL res = 0;
    for (LL l = 1, r; l <= x; l = r + 1)
    {
        r = x / (x / l);
        res = (res + Get_Sum3(x / l) * (S(r) - S(l - 1)) % p) % p;
    }
    return (res + p) % p;
}

int main()
{
    scanf("%lld%lld", &p, &n);
    Shaker(N - 5);
    inv2 = Inv(2), inv6 = Inv(6);
    printf("%lld\n", Solve(n));
    return 0;
}