公式渲染测试。

前置知识

小碎骨

艾佛森括号 $[P] = \begin{cases} 1 &\text{If P is true}\\ 0 &\text{Otherwise} \end{cases}$
此处 $P$ 是一个可真可假的命题。

引理1

$\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} + r}\right\rfloor}\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$

数论分块

内容独立了出来，详细内容见数论分块 - Luckyblock

对于一类含有 $\left\lfloor\frac{n}{i}\right\rfloor$ 的求和式 ( $n$ 为常数)，由于 $\left\lfloor\frac{n}{i}\right\rfloor$ 单调不增，故存在多个区间 $[l,r]$ , 使得 $\left\lfloor\frac{n}{i}\right\rfloor = \left\lfloor\frac{n}{j}\right\rfloor(i,j\in [l,r])$ 成立。

对于任意一个 $i$ ，最大的满足上式的 $j=\left\lfloor{\dfrac{n}{\left\lfloor{\dfrac{n}{i}}\right\rfloor}}\right\rfloor$

积性函数

定义

若 $\gcd(x,y) = 1$ 且 $f(xy)=f(x)f(y)$ ，则 $f(n)$ 为积性函数。

性质

若 $f(x)$ ， $g(x)$ 均为积性函数，则以下函数也为积性函数：
$ $\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(\dfrac{x}{d}) \end{aligned}$ $

常见积性函数

单位函数 $e(n) = [n = 1]$ 。
幂函数 $\operatorname{Id}_{k}(n) = n^k$ ， $\operatorname{id}_1(n)$ 通常简记为 $\operatorname{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}$

不是很懂上面写的什么玩意？
不用深究，有个印象继续往下看就好。

莫比乌斯函数

定义

$\mu$ 为莫比乌斯函数，定义为
$ $\mu(n) = \begin{cases} 1 &n=1\\0 &n\ \text{含有平方因子}\\(-1)^k &k\text{为}\ n\ \text{的本质不同质因子个数} \end{cases}$ $

解释

令 $n = \prod\limits_{i=1}^{k} p_{i}^{c_i}$ ，其中 $p_i$ 为质因子， $c_i\ge 1$ 。

1. $n=1$ 时， $\mu (n) = 1$ 。
2. $n\not ={1}$ 时，

$\exist i\in [1,k], c_i > 1$ 时， $\mu (n) = 0$ 。
当某质因子出现次数大于 $1$ 时， $\mu (n) = 0$ 。
$\forall i\in [1,k], c_i = 1$ 时， $\mu (n) = (-1)^k$ 。
当每个质因子只出现一次时，即 $n = \prod\limits_{i=1}^{k}p_i$ ， $\{p_i\}$ 中元素唯一。 $\mu (n) = (-1)^k$ ，此处 $k$ 为质因子的种类数。

性质

莫比乌斯函数是积性函数，且具有以下性质

$\sum_{d\mid n} \mu (d) = [n=1]$

证明，设 $n = \prod\limits_{i=1}^{k}{p_i^{c_i}}, n' = \prod\limits_{i=1}^{k}{p_i}$ 。

根据莫比乌斯函数定义，则有： $\sum\limits_{d\mid n}{\mu(d)} = \sum\limits_{d\mid n'}{\mu(d)}$ 。
若 $n'$ 的某因子 $d$ ，有 $\mu (d) = (-1)^i$ ，则它由 $i$ 个本质不同的质因子组成。
由于质因子总数为 $k$ ，满足上式的因子数为 $C_{k}^{i}$ 。
对于原求和式，转为枚举 $\mu(d)$ 的值。
则 $\sum\limits_{d\mid n'}{\mu(d)} = \sum\limits_{i=0}^{k}{C_{k}^{i} \times (-1)^i} = \sum\limits_{i=0}^{k}{C_{k}^{i} \times (-1)^i\times 1^{k-i}}$
根据二项式定理，上式 $= (1+(-1))^k$ ，
易知该式在 $k=0$ ，即 $n=0$ 时为 $1$ ，否则为 $0$ 。

反演常用结论

一个反演常用结论:
$ $[\gcd(i,j) = 1] = \sum\limits_{d\mid \gcd(i,j)} {\mu (d)}$ $

证明 1：
设 $n = \gcd(i,j)$ ，则右 $= \sum\limits_{d\mid n} {\mu (d)} = [n = 1] = [\gcd(i,j) = 1]=$ 左。

证明 2：
暴力展开： $[\gcd(i,j) = 1] = e(\gcd(i,j)) = \sum\limits_{d\mid \gcd(i,j)}\mu(d)$

线性筛求莫比乌斯函数

$\mu$ 为积性函数，因此可以线性筛莫比乌斯函数。

int pnum, mu[kMaxn], p[kMaxn];
bool vis[kMaxn];

void Euler(int lim_) {
  vis[1] = true, mu[1] = 1ll;
  for (int i = 2; i <= lim_; ++ i) {
    if (! vis[i]) {
      p[++ pnum] = i;
      mu[i] = - 1;
    }
    for (int j = 1; j <= pnum && i * p[j] <= lim_; ++ j) {
      vis[i * p[j]] = true;
      if (i % p[j] == 0) { //勿忘平方因子
        mu[i * p[j]] = 0;
        break;
      }
      mu[i * p[j]] = - mu[i];
    }
  }
}

狄利克雷(Dirichlet)卷积

建议阅读算法学习笔记(35): 狄利克雷卷积 By: Pecco。

定义两个数论函数 $f,g$ 的狄利克雷卷积为
$ $(f\ast g) (n) = \sum_{d\mid n} f(d)g(\dfrac{n}{d})$ $

性质

1. 显然满***换律，结合律，分配律。

$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$
2. $e$ 为狄利克雷卷积的单位元，有 $(f\ast e)(n) = f(n)$ 。
3. 若 $f,g$ 为积性函数，则 $f\ast g$ 为积性函数。

关于单位元 $e$

有：

$e = \mu \ast 1=\sum\limits_{d\mid n} \mu (d)$

证明

$\begin{aligned} (f\ast e)(n) = \sum_{d\mid n} f(d)e(\dfrac{n}{d}) = \sum_{d\mid n} f(d)[\dfrac{n}{d} = 1] \end{aligned}$

对于 $[\dfrac{n}{d} = 1]$ ，当且仅当 $\dfrac{n}{d}=1$ ，即 $d=n$ 时为 $1$ ，否则为 $0$ 。
则当 $d=n$ 时， $f(d)[\dfrac{n}{d}=1] = f(n)$ 。
当 $d\not ={n}$ 时， $f(d)[\dfrac{n}{d}=1] = 0$ 。

综上， $(f\ast e)(n) = \sum\limits_{d\mid n} f(d)[\dfrac{n}{d} = 1] = f(n)$ ，满足单位元的性质。
则 $e = \mu \ast 1$ 成立。

除数函数与幂函数

幂函数 $\operatorname{Id}_{k}(n) = n^k$ 。
除数函数 $\sigma_{k}(n) = \sum\limits_{d\mid n} d^k$ 。

显然有：

$(\operatorname{Id}_k\ast 1)(n) = \sum_{d\mid n} \operatorname{Id_k}(d) = \sum_{d\mid n} d^k = \sigma_k(n)$

当 $k=0$ 时， $\operatorname{Id_0}=1$ ， $\sigma_0$ 为因数个数函数，有：

$(1\ast 1)(n) = \sum_{d\mid n}1 = \sigma_0(n)$

欧拉函数与恒等函数

$\begin{aligned} \varphi \ast 1 =& \operatorname{Id}\\ \varphi =& \operatorname{Id}\ast \mu \end{aligned}$

对于一式，当 $n=p^m$ 时（ $p$ 为质数），有：

$(\varphi \ast 1)(p^m) = \sum_{d\mid n}\varphi(d) = \varphi(1) +\sum_{i=1}^{m}\varphi(p^i) = 1 +\sum_{i=1}^{m}(p^i-p^{i-1}) = p^m$

$p^i$ 的因子有 $p^{i-1}$ 个，为 $1\sim p^{i-1}$ ，故 $\varphi(p^i) = p^i-p^{i-1}$ 。

又 $(\varphi \ast 1)(n)$ 为积性函数，则对于任意正整数 $n$ ，有：

$(\varphi \ast 1)(n) = (\varphi \ast 1)(\prod p^m) = \prod(\varphi \ast 1)(p^m) = \prod p^m = n$

得证。

对于 2 式，在 1 式基础上两侧同时 $\ast \mu$ 即得。
左侧变为 $\varphi \ast 1\ast \mu = \varphi \ast e = \varphi$ 。

莫比乌斯反演

反演是个啥？反演。

公式

设 $f(n),g(n)$ 为两个数论函数。
如果有
$ $f(n) = (g\ast 1)(n) = \sum\limits_{d\mid n}{g(d)}$ $那么有$ $g(n) = (\mu \ast f)(n)=\sum\limits_{d\mid n} {\mu(d)f(\dfrac{n}{d})}$ $

证明

方法一：运用卷积。

原问题为：已知 $f = g\ast 1$ ，证明 $g = f\ast \mu$ 。
易知如下转化： $f\ast \mu = g\ast 1 \ast \mu \Longrightarrow f\ast \mu = g\ast e = g$ 。

方法二：对原式进行数论变换。

1. 用 $\sum\limits_{d\mid n}g(d)$ 替换 $f(\dfrac{n}{d})$ 。
$ $\sum_{d\mid n}{\mu(d)\sum_{k\mid \frac{n}{d}}g(k)}$ $

2. 变换求和顺序。
$ $\sum_{k\mid n}g(k)\sum_{d\mid \frac{n}{k}}{\mu(d)}$ $

3. 依据 $\sum\limits_{d\mid n}{\mu(d)} = [n=1]$ ，仅当 $\dfrac{n}{k} = 1$ 时， $\sum\limits_{d\mid \frac{n}{k}}{\mu(d)} = 1$ ，否则为 $0$ 。
此时 $k=n$ ，故上式等价于 $\sum\limits_{k\mid n} {[n=k]\cdot g(k)} = g(n)$ 。

举例

从狄利克雷(Dirichlet)卷积部分可以知道一些积性函数的关系。
尝试对它们进行反演：

$e = \mu \ast 1\iff\mu = \mu\ast e = \mu$

$\sigma_k = \operatorname{Id}_k\ast 1\iff \operatorname{Id}_k = \mu \ast \sigma_k$ $\operatorname{Id}=\varphi \ast 1\iff \varphi = \operatorname{Id}\ast \mu$

关于一类求和式

$\sum_{i=1}^{n}\sum_{j=1}^{m}f(\gcd(i,j))$

一般套路

考虑构造出函数 $g$ ，满足下列形式：

$f(n) = g\ast 1 = \sum_{d\mid n}g(d)$

则求和式变为：

$\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d\mid \gcd(i,j)}g(d)$

考虑算术基本定理，发现若满足 $d\mid \gcd (i,j)$ ，则 $d\mid i$ 且 $d\mid j$ 成立。
考虑 $g(d)$ 在何时做出贡献，调整枚举顺序：

$\sum_{d=1}g(d)\sum_{i=1}^n[d\mid i]\sum_{j=1}^m[d\mid j]$

$\sum\limits_{i=1}^{n}[d\mid i]$ 等价于 $1\sim i$ 中 $d$ 的倍数的个数，则上式等价于：

$\sum_{d=1}g(d)\left\lfloor\dfrac{n}{d}\right\rfloor\left\lfloor\dfrac{m}{d}\right\rfloor$

数论分块求解即可。

例 1

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

发现此题的 $f$ 等价于 $\operatorname{Id}$ ，则上式等价于：

$\begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^{m}\operatorname{Id}(\gcd(i,j))\\ =& \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d\mid \gcd(i,j)}\varphi(d)\\ =& \sum_{d=1}\varphi(d)\left\lfloor\dfrac{n}{d}\right\rfloor\left\lfloor\dfrac{m}{d}\right\rfloor \end{aligned}$

例 2

$\begin{aligned} &\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j) = 1]\\ =& \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}e(\gcd(i,j))\\ =& \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum_{d\mid \gcd(i,j)}\mu (d)\\ =& \sum_{d=1}\mu(d)\left\lfloor\dfrac{n}{d}\right\rfloor\left\lfloor\dfrac{m}{d}\right\rfloor \end{aligned}$

感悟

卷点什么东西，把 $g$ 卷出来。 $g$ 不一定是特殊意义的函数。

例题

[HAOI2011] Problem b

$n$ 组询问，每次给定参数 $a,b,c,d,k$ ，求：
$ $\sum\limits_{x=a}^{b}\sum\limits_{y=c}^{d}[\gcd(x,y) = k]$ 1\le n,k,a,b,c,d\le 5\times 10^4 $，$ a\le b,c\le d$。

令 $f(n,m) = \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j) = k]$ 。
根据容斥原理，则原式等价于 $f(b,d) - f(a-1,d) - f(b,d-1) + f(a-1,d-1)$ 。 $f$ 变成了上述一类求和式的形式，考虑化简 $f$ 。

易知原式等价于
$ $\sum\limits_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}[\gcd(i,j) = 1]$ $

代入反演常用结论 $[\gcd(i,j) = 1] = \sum\limits_{d\mid \gcd(i,j)} {\mu (d)}$ ，上式化为
$ $\sum\limits_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}\sum_{d\mid \gcd(i,j)}{\mu(d)}$ $变换求和顺序，先枚举$ d\mid \gcd(i,j) $，可得$ $\sum_{d=1}\mu(d)\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}[d\mid i]\sum_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}[d\mid j]$ $对于上式后半的解释：当$ d\mid i $且$ d\mid j $时，$ d\mid \gcd(i,j)$。

易知 $1\sim \left\lfloor\dfrac{n}{k}\right\rfloor$ 中 $d$ 的倍数有 $\left\lfloor\dfrac{\left\lfloor\dfrac{n}{k}\right\rfloor}{d}\right\rfloor = \left\lfloor\dfrac{n}{kd}\right\rfloor$ 个（由引理 1 可知），原式变为
$ $\sum_{d=1}\mu(d)\left\lfloor\dfrac{n}{kd}\right\rfloor\left\lfloor\dfrac{m}{kd}\right\rfloor$ $

预处理 $\mu$ 后，显然可以数论分块求解，复杂度 $O(n + T\sqrt{n})$ 。

代码

//知识点：莫比乌斯反演
/*
//By:Luckyblock
*/
#include 
#include 
#include 
#define ll long long
const int MARX = 6e4 + 10;
//=============================================================
int N, a, b, c, d, k;
int cnt, Mobius[MARX], Prime[MARX], Sum[MARX];
bool vis[MARX];
//=============================================================
inline int read()
{
    int f = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
    return f * w;
}
void GetMobius()
{
    Mobius[1] = 1;
    int MAX = MARX - 10;
    for(int i = 2; i <= MAX; i ++)
    {
      if(! vis[i]) Mobius[i] = - 1, Prime[++ cnt] = i;
      for(int j = 1; j <= cnt && i * Prime[j] <= MAX; j ++)
      {
        vis[i * Prime[j]] = true;
        if(i % Prime[j] == 0) break;
        Mobius[i * Prime[j]] = - Mobius[i];
      }
    }
    for(int i = 1; i <= MAX; i ++) Sum[i] = Sum[i - 1] + Mobius[i];
}
ll Calc(int x, int y)
{
    ll ans = 0ll; int max = std :: min(x, y);
    for(int l = 1, r; l <= max; l = r + 1)
      r = std :: min(x / (x / l), y / (y / l)),
      ans += (1ll * x / (1ll * l * k)) * (1ll * y / (1ll * l * k)) * (Sum[r] - Sum[l - 1]);
    return ans;
}
ll Solve()
{
    a = read(), b = read(), c = read(), d = read(), k = read();
    return Calc(b, d) - Calc(b, c - 1) - Calc(a - 1, d) + Calc(a - 1, c - 1);
}
//=============================================================
int main()
{ 
    N = read(); GetMobius();
    while(N --) printf("%lld\n", Solve());
    return 0;
}

[国家集训队]Crash的数字表格

给定 $n,m$ , 求：
$ $\sum_{i=1}^n\sum_{j=1}^{m} \operatorname{lcm}(i,j)\bmod 20101009$ 1\le n,m\le 10^7$。

易知原式等价于：

$\sum_{i=1}^{n}\sum_{j=1}^{m}\dfrac{ij}{\gcd (i,j)}$

考虑枚举 $\gcd(i,j)$ ，设枚举量为 $d$ 。
则 $d=\gcd(i,j)$ 的充要条件是满足 $d|i, d|j$ 且 $\gcd(\dfrac{i}{d},\dfrac{j}{d}) = 1$ ，则原式等价于：

$\sum_{i=1}^n\sum_{j=1}^m \sum_{d=1} \dfrac{ij}{d}[d|i][d|j][\gcd(\frac{i}{d}, \frac{j}{d})=1]$

先枚举 $d$ ，则原式等价于：

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

这个 $d$ 很烦人，把 $i,j$ 中的 $d$ 提出来，变为枚举 $\frac{i}{d}$ ， $\frac{j}{d}$ 。
消去 $d\mid i$ ， $d\mid j$ 的限定条件，则原式等价于：

$\begin{aligned} &\sum_{d=1}\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}[\gcd(i,j)=1]\dfrac{id\times jd}{d}\\ =& \sum_{d=1}\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}[\gcd(i,j)=1]ijd\\ =& \sum_{d=1}d \sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}[\gcd(i,j)=1]ij \end{aligned}$

单独考虑后半部分，设 $f(x,y) = \sum\limits_{i=1}^{x} \sum\limits_{j=1}^{y}[\gcd(i,j)=1]ij$ 。
发现 $f(x,y)$ 的形式与 [HAOI2011] Problem b 中的式子类似，代入 $[\gcd(i,j) = 1] = \sum\limits_{d\mid \gcd(i,j)} {\mu (d)}$ 套路一波：

$\begin{aligned} f(x,y) =& \sum\limits_{i=1}^{x} \sum\limits_{j=1}^{y}[\gcd(i,j)=1]ij\\ =& \sum_{i=1}^{x} \sum_{j=1}^{y}\sum_{d\mid \gcd(i,j)}\mu(d) ij\\ =& \sum_{d=1}\mu(d)\sum_{i=1}^{x}[d\mid i] \sum_{j=1}^{y}[d\mid j] ij\\ =& \sum_{d=1}\mu(d) d^2\sum_{i=1}^{\left\lfloor \frac{x}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{y}{d}\right\rfloor}ij \end{aligned}$

前半部分 $\sum\limits_{d=1}\mu(d) d^2$ ，可以考虑筛出 $\mu(d)$ 后求前缀和。
后半部分是等差数列乘等差数列的形式，设 $g(p,q) = \sum\limits_{i=1}^{p} \sum\limits_{j=1}^{q}ij$ ， $g_{p,q}$ 可以通过下式 $O(1)$ 计算：

$g(p,q) = \sum_{i=1}^{p} i \sum_{j=1}^{q}j= \dfrac{(1 + p)\times p}{2}\times \dfrac{(1+q)\times q}{2}$

则对于 $f(x,y)$ ，有：

$f(x,y) = \sum_{d=1}\mu(d) d^2\cdot g(\left\lfloor \frac{x}{d}\right\rfloor, \left\lfloor\frac{y}{d}\right\rfloor)$

数论分块求解即可。

再看回原式，原式等价于：

$\sum_{d=1}d\cdot f(\left\lfloor\frac{n}{d}\right\rfloor, \left\lfloor\frac{m}{d}\right\rfloor)$

又是一个可以数论分块求解的形式。
线性筛预处理后数论分块套数论分块，复杂度 $O(n + m)$ ，瓶颈是线性筛。

一些注意的点

处理时会出现求平方的运算，需要特别注意取模问题，ll 都会爆，被坑惨了。

在预处理前缀和的这个地方：

sum[i] = (sum[i - 1] + 1ll * i * i % kMod * (mu[i] + kMod)) % kMod; //仅令 mu + kMod

注意先对平方取模，在乘上 $\mu$ ，否则就会爆掉。
以及可以仅令 $mu + mod$ 。

以及这个地方：

int g(int n_, int m_) {
  return (1ll * n_ * (n_ + 1ll) / 2ll % kMod) * (1ll * m_ * (m_ + 1ll) / 2ll % kMod) % kMod;
}

平方计算，注意随时取模。

代码

//莫比乌斯反演
/*
By:Luckyblock
*/
#include 
#include 
#include 
#include 
#include 
#define ll long long
const ll kMod = 20101009;
const int kMaxn = 1e7 + 10;
//=============================================================
int pnum, p[kMaxn];
ll mu[kMaxn], sum[kMaxn];
bool vis[kMaxn];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void Getmax(int &fir_, int sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Getmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
void Euler(int lim_) {
  vis[1] = true, mu[1] = 1ll;
  for (int i = 2; i <= lim_; ++ i) {
    if (! vis[i]) {
      p[++ pnum] = i;
      mu[i] = - 1;
    }
    for (int j = 1; j <= pnum && i * p[j] <= lim_; ++ j) {
      vis[i * p[j]] = true;
      if (i % p[j] == 0) { //勿忘平方因子
        mu[i * p[j]] = 0;
        break;
      }
      mu[i * p[j]] = - mu[i];
    }
  }
  sum[1] = 1ll;
  for (int i = 1; i <= lim_; ++ i) {
    sum[i] = (sum[i - 1] + 1ll * i * i % kMod * (mu[i] + kMod)) % kMod; //仅令 mu + kMod
  }
}
int g(int n_, int m_) {
  return (1ll * n_ * (n_ + 1ll) / 2ll % kMod) * (1ll * m_ * (m_ + 1ll) / 2ll % kMod) % kMod;
}
int f(int n_, int m_) {
  int lim = std :: min(n_, m_), ret = 0;
  for (int l = 1, r; l <= lim; l = r + 1) {
    r = std :: min(n_ / (n_ / l), m_ / (m_ / l));
    ret = (ret + 1ll * (sum[r] - sum[l - 1] + kMod) * g(n_ / l, m_ / l) % kMod) % kMod;
  }
  return ret;
}
int Sum(ll l, ll r) {
  return (1ll * (r - l + 1ll) * (l + r) / 2ll) % kMod;
}
//=============================================================
int main() { 
  int n = read(), m = read();
  int lim = std :: min(n, m), ans = 0;
  Euler(lim);
  for (int l = 1, r; l <= lim; l = r + 1) {
    r = std :: min(n / (n / l), m / (m / l));
    ans = (ans + 1ll * Sum(l, r) * f(n / l, m / l) % kMod) % kMod;
  }
  printf("%d", ans);
  return 0;
}
/*
7718820 8445880
*/

SP5971 LCMSUM - LCM Sum

$T$ 次询问，每次询问给定 $n$ ，求：
$ $\sum_{i=1}^{n}\operatorname{lcm}(i,n)$ 1<T\le 3\times 10^5 $，$ 1\le n\le 10^6$。

法一：无脑暴力

先拆 $\operatorname{lcm}$ ，原式等价于：

$n\sum_{i=1}^{n}\dfrac{i}{\gcd(i,n)}$

套路的枚举 $\gcd(i,n)$ ，调换枚举顺序，原式等价于：

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

把 $i,n$ 中的 $d$ 提出来，变为枚举 $\frac{i}{d}$ ，消去整除的条件，原式等价于：

$n\sum_{d|n}\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[\gcd(i,\dfrac{n}{d}) = 1]i$

代入 $[\gcd(i,j) = 1] = \sum\limits_{d\mid \gcd(i,j)} {\mu (d)}$ ，原式等价于：

$n\sum_{d|n}\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor} i \sum_{t|\gcd(i,\frac{n}{d})}\mu (t)$

值得注意的是 $t$ 的上界为 $\frac{n}{d}$ ， $dt\le n$ 。
调换枚举顺序，先枚举 $t$ ，原式等价于：

$n\sum_{d|n}\sum_{t|\frac{n}{d}} \mu(t) \sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor} [t|i] i$

套路地消去整除的条件，把 $i$ 中的 $t$ 提出来，原式等价于：

$n\sum_{d|n}\sum_{t|\frac{n}{d}} \mu(t)t \sum_{i=1}^{\left\lfloor\frac{n}{dt}\right\rfloor} i$

对于最后的一个求和项，设 $g(x) = \sum\limits_{i=1}^{x}i = \frac{x(x+1)}{2}$ ，显然可以 $O(1)$ 求解，原式等价于：

$n\sum_{d|n}\sum_{t|\frac{n}{d}} \mu(t)t\cdot g(\left\lfloor\dfrac{n}{dt}\right\rfloor)$

考虑枚举 $T = dt$ ，显然 $T\le n$ 。 $\mu(t)t$ 与 $d$ 无关，可以直接考虑枚举 $t|T$ ，原式等价于：

$n\sum_{T=1}^{n}g(\left\lfloor\dfrac{n}{T}\right\rfloor)\sum_{t|T}\mu(t)t$

前半块是一个数论分块的形式，可以 $O(\sqrt{n})$ 求解。
考虑后半块，设 $f(n)=\sum\limits_{d|n}\mu(d)d$ ，发现它是一个积性函数，可以线性筛筛出，具体地：

$f(n)= \begin{cases} 1-n &n\in \mathrm{primes} \\ f(\frac{x}{p}) &p^2\mid n\\ f(\frac{x}{p})f(p) &p^2\nmid n \end{cases}$

其中 $p$ 为 $n$ 的最小质因子。

此时已经可以线性筛 + 数论分块求解，复杂度 $O(n+T\sqrt{n})$ ，比较菜鸡，时限 500ms 过不了。
考虑筛出 $f$ 后再用埃氏筛预处理 $\sum\limits_{T=1}^{n}g(\left\lfloor\dfrac{n}{T}\right\rfloor)f(T)$ ，输出时乘上 $n$ ，复杂度变为 $O(n\log^2 n + n)$ 。

法二：

同样先拆 $\operatorname{lcm}$ ，枚举 $\gcd(i,n)$ ，调换枚举顺序，原式等价于：

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

把 $i,n$ 中的 $d$ 提出来，变为枚举 $\frac{i}{d}$ ，消去整除的条件，原式等价于：

$\begin{aligned} &n\sum_{d|n}\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[\gcd(id,n) = d]i\\ =& n\sum_{d|n}\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[\gcd(i,\dfrac{n}{d}) = 1]i \end{aligned}$

调整枚举对象，上式等价于：

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

考虑 $\sum\limits_{i=1}^{d}[\gcd(i,d) = 1]i$ 的实际意义，表示 $[1,d]$ 中与 $d$ 互质的数的和。
当 $d>1$ 时，与 $d$ 互质的数总是成对存在，即若 $\gcd(i,d)=1$ 成立，则 $\gcd(d-i,d)=1$ 成立。
每对这样的数的和为 $d$ ，共有 $\frac{\varphi(d)}{2}$ 对这样的数。
则原式等价于：
$ $n\sum_{d|n}\dfrac{\varphi(d)d}{2}$ $

可以直接预处理答案。
预处理时先线性筛出 $\varphi$ ，再埃氏筛枚举 $i$ 的倍数，令它们的答案加上 $\frac{\varphi(i)i}{2}$ ，最后输出时乘上 $n$ 。
复杂度 $O(n\log^2 n + T)$ 。

法二代码

//知识点：莫比乌斯反演
/*
By:Luckyblock
*/
#include 
#include 
#include 
#include 
#define ll long long
const int kMaxn = 1e6;
//=============================================================
ll phi[kMaxn + 10], ans[kMaxn + 10];
int pnum, p[kMaxn + 10];
bool flag[kMaxn + 10];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void GetMax(int &fir, int sec) {
  if (sec > fir) fir = sec;
}
void GetMin(int &fir, int sec) {
  if (sec < fir) fir = sec;
}
void GetPrime() {
  phi[1] = 1, flag[1] = true; //注意初始化
  for (int i = 2; i <= kMaxn; ++ i) {
    if (! flag[i]) {
      p[++ pnum] = i;
      phi[i] = i - 1ll;
    }
    for (int j = 1; j <= pnum && i * p[j] <= kMaxn; ++ j) {
      flag[i * p[j]] = true;
      if (i % p[j]) {
        phi[i * p[j]] = phi[i] * phi[p[j]];
      } else {
        phi[i * p[j]] = phi[i] * p[j];
        break;
      }
    }
  }
  for (int i = 1; i <= kMaxn; ++ i) {
    for (int j = 1; i * j <= kMaxn; ++ j) {
      ans[i * j] += (i == 1 ? 1 : 1ll * phi[i] * i / 2);
    }
  }
}
//=============================================================
int main() { 
  GetPrime();
  int T = read();
  while (T --) {
    int n = read();
    printf("%lld\n", 1ll * ans[n] * n);
  }
  return 0; 
}

[SDOI2015]约数个数和

$T$ 次询问，每次询问给定 $n,m$ 。
定义 > $\operatorname{d}(i)$ 为 $i$ 的约数个数，求：
$ $\sum_{i=1}^{n}\sum_{j=1}^m\operatorname{d}(ij)$ 1<T,n\le 5\times 10^4$。

一个结论：

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

证明

先考虑 $i = p^a$ ， $j=p^b(p\in \mathrm{primes})$ 的情况，有：

$\operatorname{d}(p^{a+b})=\sum_{x|p^a}\sum_{y|p^b}[\gcd(x,y)=1]$

对于等式左侧， $p^{a+b}$ 的约数个数为 $a+b+1$ 。
对于等式右侧，在保证 $\gcd(x,y)=1$ 成立的情况下，有贡献的数对 $(x,y)$ 只能是下列三种形式：

$x>0,y-0$ ， $x$ 有 $a$ 种取值方法。
$x=0,y>0$ ， $y$ 有 $b$ 种取值方法。
$x=0,y=0$ 。

则等式右侧贡献次数为 $a+b+1$ 次，等于 $p^{a+b}$ 的约数个数。
则当 $i = p^a$ ， $j=p^b(p\in \mathrm{primes})$ 时等式成立。

又不同质因子间相互独立，上述情况可拓展到一般的情况。

对 $\operatorname{d}(i,j)$ 进行化简，代入 $[\gcd(i,j) = 1] = \sum\limits_{d\mid \gcd(i,j)} {\mu (d)}$ ，原式等价于：

$\begin{aligned} \operatorname{d}(ij) =& \sum_{x|i}\sum_{y|j}[\gcd(x,y)=1]\\ =& \sum_{x|i}\sum_{y|j}\sum\limits_{d\mid \gcd(x,y)} {\mu (d)} \end{aligned}$

调换枚举顺序，先枚举 $d$ ，原式等价于：

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

把各项中的 $d$ 提出来，消去整除的条件，原式等价于：

$\begin{aligned} &\sum_{d=1}[d|i][d|j]{\mu (d)}\sum_{x|\frac{i}{d}}\sum_{y|\frac{j}{d}}1\\ =& \sum_{d=1}[d|i][d|j]{\mu (d)}\cdot \operatorname{d}(\dfrac{i}{d})\operatorname{d}(\dfrac{j}{d}) \end{aligned}$

将 $\operatorname{d}(ij)$ 代回原式，原式等价于：

$\sum_{i=1}^{n}\sum_{j=1}^m \sum_{d=1}[d|i][d|j]{\mu (d)}\cdot \operatorname{d}(\dfrac{i}{d})\operatorname{d}(\dfrac{j}{d})$

调换枚举顺序，先枚举 $d$ ，原式等价于：

$\sum_{d=1}{\mu (d)}\sum_{i=1}^{n}[d|i]\sum_{j=1}^m [d|j]\cdot \operatorname{d}(\dfrac{i}{d})\operatorname{d}(\dfrac{j}{d})$

把 $i,j$ 中的 $d$ 提出来，变为枚举 $\frac{i}{d}, \frac{j}{d}$ ，消去整除的条件，原式等价于：

$\sum_{d=1}{\mu (d)}\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\operatorname{d}(i)\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}\operatorname{d}(j)$

考虑预处理 $S(x) = \sum\limits_{i=1}^{x}\operatorname{d}(i)$ ，则原式等价于：

$\sum_{d=1}{\mu (d)}S\left({\left\lfloor\frac{n}{d}\right\rfloor}\right)S\left({\left\lfloor\frac{m}{d}\right\rfloor}\right)$

线性筛预处理 $\mu,\operatorname{d}$ ，数论分块求解即可，复杂度 $O(n+T\sqrt{n})$ 。

代码

//知识点：莫比乌斯反演
/*
By:Luckyblock
*/
#include 
#include 
#include 
#include 
#include 
#define ll long long
const int kMaxn = 5e4 + 10;
//=============================================================
int pnum, p[kMaxn];
ll mu[kMaxn], num[kMaxn], d[kMaxn]; //num 为最小质因子的次数
ll summu[kMaxn], sumd[kMaxn];
bool vis[kMaxn];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void Getmax(int &fir_, int sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Getmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
void Euler(int lim_) {
  vis[1] = true;
  mu[1] = d[1] = 1ll;
  for (int i = 2; i <= lim_; ++ i) {
    if (! vis[i]) {
      p[++ pnum] = i;
      mu[i] = - 1;
      num[i] = 1;
      d[i] = 2;
    }
    for (int j = 1; j <= pnum && i * p[j] <= lim_; ++ j) {
      vis[i * p[j]] = true;
      if (i % p[j] == 0) { //勿忘平方因子
        mu[i * p[j]] = 0;
        num[i * p[j]] = num[i] + 1;
        d[i * p[j]] = 1ll * d[i] / num[i * p[j]] * (num[i * p[j]] + 1ll);
        break;
      }
      mu[i * p[j]] = - mu[i];
      num[i * p[j]] = 1;
      d[i * p[j]] = 2ll * d[i]; //

    }
  }
  for (int i = 1; i <= lim_; ++ i) {
    summu[i] = summu[i - 1] + mu[i];
    sumd[i] = sumd[i - 1] + d[i];
  }
}

//=============================================================
int main() { 
  Euler(kMaxn - 10);
  int T = read();
  while (T --) {
    int n = read(), m = read(), lim = std :: min(n, m);
    ll ans = 0ll;
    for (int l = 1, r; l <= lim; l = r + 1) {
      r = std :: min(n / (n / l), m / (m / l));
      ans += 1ll * (summu[r] - summu[l - 1]) * sumd[n / l] * sumd[m / l]; //
    }
    printf("%lld\n", ans);
  }
  return 0;
}
/*
in
1
32 43
*/
/*
out
15420
*/

P3768 简单的数学题

给定参数 $n$ 、 $p$ ，求：
$ $\left(\sum_{i=1}^n\sum_{j=1}^ni\cdot j\cdot \gcd(i,j)\right)\bmod p$ n\leq10^{10} $，$ 5\times10^8\leq p\leq1.1\times10^9 $，$ p\in \mathrm{primes}$。
时限 4s。

无脑套路暴力。

考虑先枚举 $\gcd(i,j)$ ，原式等价于：

$\begin{aligned} &\sum_{d=1}d\sum_{i=1}^{n}\sum_{j=1}^{n}[\gcd(i,j)=d]ij\\ =& \sum_{d=1}d\sum_{i=1}^{n}[d|i]\sum_{j=1}^{n}[d|j][\gcd(\dfrac{i}{d},\dfrac{j}{d})=1]ij \end{aligned}$

提出 $d$ ，变为枚举 $\frac{i}{d}$ 与 $\frac{j}{d}$ ，消去整除的条件，原式等价于：

$\begin{aligned} &\sum_{d=1}d\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[\gcd(i,j)=1]id\cdot jd\\ =& \sum_{d=1} d^3\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[\gcd(i,j)=1]ij \end{aligned}$

代入 $[\gcd(i,j) = 1] = \sum\limits_{d\mid \gcd(i,j)} {\mu (d)}$ ，原式等价于：

$\sum_{d=1} d^3\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}ij\sum_{t|\gcd(i,j)}\mu (t)$

值得注意的是 $t$ 的上界为 $\frac{n}{d}$ ， $dt\le n$ 。
调换枚举顺序，先枚举 $t$ ，原式等价于：

$\sum_{d=1} d^3\sum_{t=1}\mu(t)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[t|i] \sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[t|j]ij$

和上面一样，提出 $t$ ，套路地消去整除的条件，原式等价于：

$\sum_{d=1} d^3\sum_{t=1}\mu(t)t^2\sum_{i=1}^{\left\lfloor\frac{n}{dt}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{dt}\right\rfloor}ij$

发现后面两个求和是等差数列乘等差数列的形式。
设 $g(p,q) = \sum\limits_{i=1}^{p} \sum\limits_{j=1}^{q}ij$ ， $g_{p,q}$ 可以通过下式 $O(1)$ 计算：

$g(p,q) = \sum_{i=1}^{p} i \sum_{j=1}^{q}j= \dfrac{(1 + p)\times p}{2}\times \dfrac{(1+q)\times q}{2}$

代入原式，原式等价于：

$\sum_{d=1} d^3\sum_{t=1}\mu(t)t^2\cdot g\left({\left\lfloor\frac{n}{dt}\right\rfloor},{\left\lfloor\frac{n}{dt}\right\rfloor}\right)$

考虑枚举 $T = dt$ ，显然 $T\le n$ 。
再考虑枚举 $d|T$ ，即可得到 $t = \frac{T}{d}$ ，原式等价于：

$\begin{aligned} &\sum_{T=1}^{n}g\left({\left\lfloor\frac{n}{T}\right\rfloor},{\left\lfloor\frac{n}{T}\right\rfloor}\right)\sum_{d|T}d^3\mu{\left(\dfrac{T}{d}\right)}\left(\dfrac{T}{d}\right)^2\\ =& \sum_{T=1}^{n}T^2 g\left({\left\lfloor\frac{n}{T}\right\rfloor},{\left\lfloor\frac{n}{T}\right\rfloor}\right)\sum_{d|T}d\cdot \mu{\left(\dfrac{T}{d}\right)} \end{aligned}$

对于后面这一坨，用 $\sum\limits_{d|T}d\cdot \mu{\left(\frac{T}{d}\right)} = \operatorname{Id} \ast \mu(T)= \varphi(T)$ 反演，则原式等价于：

$\sum_{T=1}^{n}T^2 \varphi(T) \cdot g\left({\left\lfloor\frac{n}{T}\right\rfloor},{\left\lfloor\frac{n}{T}\right\rfloor}\right)$

后半块可以数论分块，考虑前半块。
发现前半段即为 $\operatorname{Id}^2(T)\varphi(T)$ ，又是前缀和形式，考虑杜教筛。

有：

$f(n) = \operatorname{Id}^2\varphi(n)$

考虑找到一个函数 $g$ ，构造函数 $h = f\ast g$ 使其便于求值，有：

$h(n) = \sum_{d|n} d^2\varphi(d)\cdot g\left(\dfrac{n}{d}\right)$

看到同时存在 $d$ 和 $\frac{n}{d}$ ，考虑把 $d^2$ 消去。
令 $g = \operatorname{Id}^2$ ，有：

$\begin{aligned} h(n) =& \sum_{d|n} d^2\varphi(d)\cdot \left(\dfrac{n}{d}\right)^2\\ =& n^2\sum_{d|n} \varphi(d)\\ =& n^2 \cdot \varphi \ast 1(n)\\ \end{aligned}$

又 $\varphi \ast 1 = \operatorname{Id}$ ，则有：

$h(n) = n^3$

找到了合适的 $g$ ，套杜教筛的公式。

$\begin{aligned} g(1)S(n) &= \sum_{i=1}^{n}h(i) - \sum_{i=2}^{n}g(i)S\left(\left\lfloor\dfrac{n}{i}\right\rfloor\right)\\ S(n) &= \sum_{i=1}^{n} i^3 - \sum_{i=2}^{n} i^2\cdot S\left(\left\lfloor\dfrac{n}{i}\right\rfloor\right) \end{aligned}$

前一项是自然数的立方和，有 $\sum\limits_{i=1}^{n} i^3 = (\frac{n(n+1)}{2})^2$ 。证明详见：自然数前n项平方和、立方和公式及证明 - 百度文库。
后一项直接等差数列求和 + 数论分块求解即可。

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

因为非常喜欢这首曲子所以很想写下这题。
但是先咕咕咕咕着。

写在最后

参考资料：
Oi-Wiki-莫比乌斯反演
 算法学习笔记(35): 狄利克雷卷积 By: Pecco
题解 SP5971 【LCMSUM - LCM Sum】 - BJpers2 的博客
 题解 SP5971 【LCMSUM - LCM Sum】 - Venus 的博客
 题解 P3327 【[SDOI2015]约数个数和】 - suncongbo 的博客

把 Oi-Wiki 上的内容进行了复制整理扩充。
~~我是个没有感情的复读机(大雾)~~