1. 定义
1.1 基础定义
- 数论函数：定义域为正整数的函数称为数论函数。因其在所有正整数处均有定义，故可视作数列。
- 加性函数：若 \(\forall a,b\in\mathbb{N}^{+},a\perp b,f(ab)=f(a)+f(b)\)，则称 \(f\) 为加性函数。
- 积性函数：若 \(\forall a,b\in\mathbb{N}^{+},a\perp b,f(ab)=f(a)f(b)\)，则称 \(f\) 为积性函数。
- 完全积性函数：若 \(\forall a,b\in\mathbb{N}^{+},f(ab)=f(a)f(b)\)，则称 \(f\) 为完全积性函数。
- 数论函数的加法：对于数论函数 \(f,g\)，\(f+g\) 表示对应位置相加，即 \((f+g)(x)=f(x)+g(x)\)。
- 数论函数的数乘：对于数 \(c\) 和数论函数 \(f\)，\(c\cdot f\) 表示 \(f\) 的各个位置乘 \(c\)，即 \((c\cdot f)(x)=c\cdot f(x)\)，一般简记为 \(cf\)。
- 数论函数的点乘：对于数论函数 \(f,g\)，\(f\cdot g\) 表示 \(f\) 和 \(g\) 各个位置相乘，即 \((f\cdot g)(x)=f(x)g(x)\)，通常不省略。
1.2 常见数论函数
-
单位函数：\(\varepsilon(n)=[n=1]\)。它是完全积性函数。
-
常数函数：\(\boldsymbol 1(n)=1\)。它是完全积性函数。
-
恒等函数：\(\text{id}_{k}(n)=n^{k}\)。\(\text{id}_1(n)\) 记作 \(\text{id}(n)\)。它是完全积性函数。
-
除数函数：\(\sigma_k(n)=\sum\limits_{d\mid n}d^k\)。\(\sigma_0(n)\) 表示 \(n\) 的约数个数，记作 \(\tau(n)\) 或 \(d(n)\)。\(\sigma_1(n)\) 表示 \(n\) 的约数和，记作 \(\sigma(n)\)。
-
欧拉函数：\(\varphi(n)=\sum\limits_{i=1}^{n}[i\perp n]\)。表示 \(n\) 以内与 \(n\) 互质的个数，是积性函数。
-
本质不同质因子个数函数：\(\omega(n)=\sum\limits_{p\in\mathbb{P}}[p\mid n]\)。表示 \(n\) 的本质不同质因子个数，是加性函数。
-
莫比乌斯函数：\(\mu(n)=\begin{cases}1&n=1\\0&\exists d>1,d^2\mid n\\(-1)^{\omega(n)}&\mathrm{otherwise} \end{cases}\)。
2. 线性筛
在 \(O(n)\) 的时间内筛出某些玩意。
2.1 线性筛素数
保证每个数只被最小质因子筛掉。
inline void getPrime(){
int w=N-1;
for(int i=2;i<=w;i++){
if(!vis[i])
pr[++tot]=i;
for(int j=1;j<=tot and i*pr[j]<=w;j++){
vis[i*pr[j]]=1;
if(i%pr[j]==0)
break;
}
}
}
2.2 线性筛莫比乌斯函数
\(\mu(1)=1\)；\(i\) 为质数时 \(\mu(i)=-1\)，最小质因子筛到的时候比 \(i\) 多了一个质数所以反过来。
inline void getMu(){
int w=N-1;mu[1]=1;
for(int i=2;i<=w;i++){
if(!vis[i]){
pr[++tot]=i;
mu[i]=-1;
}
for(int j=1;j<=tot and i*pr[j]<=w;j++){
vis[i*pr[j]]=1;
if(i%pr[j]==0){
mu[i*pr[j]]=0;
break;
}
mu[i*pr[j]]=-mu[i];
}
}
}
2.3 线性筛欧拉函数
若 \(p\mid n\) 则 \(n\) 含有 \(np\) 所有的质因子，所以 \(\varphi(np)=p\times n\prod\limits_{i=1}^k\left(1-\dfrac{1}{p_i}\right)=p\times\varphi(n)\)。
若 \(p\nmid n\) 则 \(\varphi(np)=\varphi(n)\times\varphi(p)=(p-1)\times\varphi(n)\)。
inline void getPhi(){
int w=N-1;phi[1]=1;
for(int i=2;i<=w;i++){
if(!vis[i]){
pr[++tot]=i;
phi[i]=i-1;
}
for(int j=1;j<=tot and i*pr[j]<=w;j++){
vis[i*pr[j]]=1;
phi[i*pr[j]]=phi[i]*(pr[j]-(i%pr[j]?1:0));
if(i%pr[j]==0)
break;
}
}
}
2.4 线性筛约数个数
令 \(n=\prod\limits_{i=1}^kp_i^{a_i}\)，则 \(\tau(n)=\prod\limits_{i=1}^k(a_i+1)\)。
只要记录每个数最小质因数的指数。
inline void getTau(){
int w=N-1;T[1]=1;
for(int i=2;i<=w;i++){
if(!vis[i]){
pr[++tot]=i;
T[i]=2;a[i]=1;
}
for(int j=1;j<=tot and i*pr[j]<=w;j++){
vis[i*pr[j]]=1;
if(i%pr[j]){
T[i*pr[j]]=T[i]*T[pr[j]];
a[i*pr[j]]=1;
}else{
T[i*pr[j]]=T[i]/(a[i]+1)*(a[i]+2);
a[i*pr[j]]=a[i]+1;
break;
}
}
}
}
3. 狄利克雷卷积
狄利克雷（Dirichlet）卷积是数论函数的基本运算。
3.1 定义和性质
定义狄利克雷卷积为
\[h(n)=\sum\limits_{d\mid n}f\left(d\right)g\left(\dfrac{n}{d}\right) \]简记为 \(h=f*g\)。按照定义式计算狄利克雷卷积，时间复杂度为调和级数 \(\mathcal{O}(n\ln n)\)。
狄利克雷卷积有如下几个性质：
- 狄利克雷卷积具有 交换律，结合律，分配律。
- \(\varepsilon*f=f\)。 因此单位函数 \(\varepsilon\) 为狄利克雷卷积的 单位元，也可以定义数论函数的逆元 \(f^{-1}\) 满足 \(f*f^{-1}=\varepsilon\)。
- 数论函数 \(f\) 存在逆元 当且仅当 \(f(1)\) 非零。
- \(f=g\) 的充要条件是 \(f*h=g*h\)，其中数论函数 \(h(x)\) 要满足 \(h(1)\) 非零。
- 积性函数的狄利克雷卷积是积性函数。
- 积性函数的逆元是积性函数。综合性质 5 和性质 6，可以得到两个积性函数的积与商都是积性函数。
3.2 狄利克雷前缀和
任意数论函数 \(f\) 卷常数函数 \(\boldsymbol 1\) 等价于对 \(f\) 做狄利克雷前缀和，即：令 \(g=f*\boldsymbol 1\)，则 \(g(n)=\sum\limits_{d\mid n}f(d)\)。
将每个 \(n\) 写成无穷序列 \(a_n=\{c_1,c_2,\cdots,c_i,\cdots\}\) 表示 \(n=\prod p_i^{c_i}\)，其中 \(p_i\) 表示第 \(i\) 个质数。因为 \(x\mid y\) 的充要条件为 \(a_x(c_i)\leq a_y(c_i)\)，所以 \(f*\boldsymbol 1\) 可以看成对下标做关于其无穷序列的高维前缀和，即：\(g(n)=\sum\limits_{\forall i,a_d(c_i)\leq a_n(c_i)}f(d)\)。
实现方法：初始令 \(x_i=f(i)\)。行销到达枚举每个质数 \(p_i\)，枚举 \(k\)，将 \(x_{p,k}\) 加上 \(x_k\)，相当于 \(k\) 贡献到 \(a_k(i)\) 加上 \(1\) 之后的下标。最终得到的 \(x\) 即为 \(g\)。
根据小于 \(n\) 的素数倒数和为 \(\ln\ln n\) 这一结论，狄利克雷前缀和的时间复杂度为 \(\mathcal{O}(n\ln\ln n)\)。
const int N=2e7+5;
int n,vis[N],pr[N>>3],tot;
unsigned ans,a[N],seed;
inline void getPrime(){
for(int i=2;i<=n;i++){
if(!vis[i])
pr[++tot]=i;
for(int j=1;j<=tot and i*pr[j]<=n;j++){
vis[i*pr[j]]=true;
if(i%pr[j]==0)
break;
}
}
}
inline unsigned getnext(){
seed^=seed<<13;
seed^=seed>>17;
seed^=seed<<5;
return seed;
}
signed main(){
cin>>n>>seed;
getPrime();
for(int i=1;i<=n;i++)
a[i]=getnext();
for(int i=1;i<=tot;i++)
for(int j=1;j*pr[i]<=n;j++)
a[j*pr[i]]+=a[j];
for(int i=1;i<=n;i++)
ans^=a[i];
cout<<ans<<'\n';
return 0;
}
4. 数论分块
4.1 算法介绍
数论分块又称整除分块，因其解决的问题与整除密切相关而得名。数论分块用于求解形如
\[\sum\limits_{i=1}^{n}f(i)g\left(\left\lfloor\dfrac{n}{i}\right\rfloor\right) \]的和式。前提为 \(f\) 的前缀和可以快速计算。
引理1
\[\forall a,b,c\in\mathbb{Z}, \left\lfloor\dfrac{a}{bc}\right\rfloor= \left\lfloor\dfrac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor \]
证明：
\[\begin{aligned}& \because\dfrac{a}{b}= \left\lfloor\dfrac{a}{b}\right\rfloor+r\ (0\leq r<1) \\&\therefore\left\lfloor\dfrac{a}{bc}\right\rfloor= \left\lfloor\dfrac{a}{b}\times\dfrac{1}{c}\right\rfloor= \left\lfloor\dfrac{1}{c}\left(\dfrac{a}{b}+r\right)\right\rfloor= \left\lfloor\dfrac{\left\lfloor\frac{a}{b}\right\rfloor}{c}+\dfrac{r}{c}\right\rfloor= \left\lfloor\dfrac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor \end{aligned} \]引理2
\[\forall n\in\mathbb{N}_+, \left\lvert\left\{ \left\lfloor\dfrac{n}{d}\right\rfloor \mid d\in\mathbb{N_+},d\leq n\right\}\right\rvert\leq \left\lfloor2\sqrt{n}\right\rfloor \]
证明：
-
对于 \(d\leq \left\lfloor\sqrt{n}\right\rfloor\)，有 \(\left\lfloor\sqrt{n}\right\rfloor\) 种取值。
-
对于 \(d> \left\lfloor\sqrt{n}\right\rfloor\)，有 \(\left\lfloor\frac{n}{d}\right\rfloor\leq\left\lfloor\sqrt{n}\right\rfloor\)，也只有$ \left\lfloor\sqrt{n}\right\rfloor$ 种取值。
4.2 数论分块结论
对于常数 \(n\)，使得式子
\[\left\lfloor\dfrac ni\right\rfloor=\left\lfloor\dfrac nj\right\rfloor \]成立且满足 \(i\leq j\leq n\) 的 \(j\) 值最大为 \(\left\lfloor\dfrac n{\lfloor\frac ni\rfloor}\right\rfloor\)，即值 \(\left\lfloor\dfrac ni\right\rfloor\) 所在块的右端点为 \(\left\lfloor\dfrac n{\lfloor\frac ni\rfloor}\right\rfloor\)。
4.3 过程
考虑计算式子
\[\sum\limits_{i=1}^{n}f(i)\left\lfloor\dfrac{n}{i}\right\rfloor \]因为 \(\left\lfloor\dfrac{n}{i}\right\rfloor\) 的值成块状分布，那么就可以用数论分块加速计算。具体地先求出 \(f\) 的前缀和 \(s\)，然后每次以 \([l,r]=\left[l,\left\lfloor\dfrac n{\lfloor\frac ni\rfloor}\right\rfloor\right]\) 为一块，分块求出贡献累加到结果中。
每个整除值会且仅会被遍历一次，时间复杂度为 \(\mathcal O(\sqrt n)\)。
当 \(i\) 的上界不为 \(n\) 时，设其为 \(m\)，则当 \(n>m\) 时 \(r\) 应与 \(m\) 取较小值，当 \(n<m\) 时特盘 \(\left\lfloor\dfrac ni\right\rfloor=0\) 的情况并令 \(r\leftarrow m\)。
4.4 扩展
4.4.1 向上取整
对于常数 \(n\)，使得式子
\[\left\lceil\dfrac ni\right\rceil=\left\lceil\dfrac nj\right\rceil \]成立且满足 \(i\leq j\leq n\) 的 \(j\) 值最大为 \(\left\lfloor\dfrac {n-1}{\lfloor\frac {n-1}i\rfloor}\right\rfloor\)，即值 \(\left\lceil\dfrac ni\right\rceil\) 所在块的右端点为 \(\left\lfloor\dfrac {n-1}{\lfloor\frac {n-1}i\rfloor}\right\rfloor\)。
4.4.2 高维数论分块
当式子中出现若干下取整，形如
\[\sum\limits_{i=1}^{n}f(i)\prod\limits_{j=1}^{c}g\left(\left\lfloor\dfrac {n_j}i\right\rfloor\right) \]时，令 \(r=\min\limits_{j=1}^c\left(\left\lfloor\dfrac{n_j}{\left\lfloor\frac{n_j} l\right\rfloor}\right\rfloor\right)\) 即可。对 \(n\) 取 \(\min\)。时间复杂度为 \(\mathcal O\left(\sum\sqrt{n_j}\right)\)。
5. 莫比乌斯函数
\[\mu(n)=\begin{cases}1&n=1\\0&\exists d>1,d^2\mid n\\(-1)^{\omega(n)}&\mathrm{otherwise} \end{cases} \]对 \(\mathbb N\) 做容斥，得到贡献系数为 \(\mu\)。
5.1 莫比乌斯反演
\(\mu*1=\varepsilon\) 引出了 \(\mu\) 的关键性质：\([n=1]=\varepsilon(n)=\sum\limits_{d\mid n}\mu(d)\)。这使得我们可以用 \(\mu\) 的和式代替形如 \(\left[n=x\right]\) 的的艾佛森括号，体现出其反演的核心。
一些结论：
- 若 \(g(n)=\sum\limits_{d\mid n}f(d)\)，则 \(f(n) = \sum\limits_{d\mid n} \mu(d) f\left(\dfrac n d\right)\)，即若 \(g=f*1\)，则 \(f=g*u\)。
- 若 \(g(n) = \sum\limits_{n\mid d} f(d)\)，则 \(f(n) = \sum\limits_{n\mid d} \mu\left(\dfrac d n\right) g(d)\)，因为 \(\sum\limits_{n\mid d} \mu\left(\dfrac d n\right) \sum\limits_{d\mid k} f(k) = \sum\limits_{n\mid k} f(k) \sum\limits_{d\mid \frac k n} \mu(d) = f(n)\)。
- 因为 \(\varphi * \boldsymbol1 = \mathrm{id}\)，所以 \(\mathrm{id} * \mu = \varphi\)，即 \(\sum\limits_{d \mid n} \dfrac n d \mu(d) = \varphi(n)\)，或 \(\sum\limits_{d\mid n} \dfrac{\mu(d)} d = \dfrac {\varphi(n)} n\)。
5.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 \sum\limits_{d\mid \gcd(i, j)} \mu(d) \\ & = \sum\limits_{d = 1} ^ {\min(n, m)} \mu(d) \sum\limits_{i = 1} ^ n \sum\limits_{j = 1} ^ m [d\mid i\land d\mid j] \\ & = \sum\limits_{d = 1} ^ {\min(n, m)} \mu(d) \left\lfloor \dfrac n d \right\rfloor \left\lfloor \dfrac m d \right\rfloor \\ \end{aligned} \]
相当于对 “最大公约数为 \(d\) 的倍数” 中的 \(d\) 做容斥，加上最大公约数为 \(1\) 的倍数的对数，减去最大公约数为 \(p_i\) 的倍数的对数，加上最大公约数为 \(p_ip_j\) 的倍数的对数，以此类推，得到每个 \(d\) 的贡献系数即莫比乌斯函数。
\[\tau(ij) = \sum\limits_{x \mid i}\sum\limits_{y\mid j}[\gcd(x,y)=1] \]
考虑把每个因子一一映射。
如果 \(ij\) 的因子 \(k\) 中有一个因子 \(p^c\)，\(i\) 中有因子 \(p^a\)，\(j\) 中有因子 \(p^b\)。我们规定：
- 如果 \(c\leq a\)，那么在 \(i\) 中选择。
- 如果 \(c>a\)，那么把 \(c\) 减去 \(a\)，在 \(j\) 中选择 \(p^{c-a}\)。
对于 \(ij\) 的因子 \(k\) 的其他因子同理。于是对于任何一个 \(k\) 都有一个唯一的映射，且每一个选择对应着唯一的 \(k\)。
通过如上过程，我们发现：对于 \(ij\) 的因子 \(k=\prod p_i^{c_i}\)，不可能同时在 \(i\) 和 \(j\) 中同时选择 \(p_i\)（优先在 \(i\) 中选择，如果不够就只在 \(j\) 中选择不够的指数），所以 \(x,y\) 互质。
5.3 例题
以下所有分式均省略下取整符号。题单
I. P2522 [HAOI2011] Problem b
求：
\[\sum\limits_{i=a}^{b}\sum\limits_{j=c}^{d}[\gcd(i,j)=k] \]二维差分将式子下界化为 \(1\)，然后推式子：
\[\sum_{i = 1} ^ n \sum_{j = 1} ^ m [\gcd(i, j) = k] \]莫反得
\[\sum_{i = 1} ^ {\frac n k} \sum_{j = 1} ^ {\frac m k} \sum_{d\mid \gcd(i, j)} \mu(d) \]枚举约数 \(d\)，记 \(c=\min\left(\dfrac{n}{k},\dfrac{m}{k}\right)\)，
\[\sum_{d = 1} ^ c \mu(d) \sum_{i = 1} ^ {\frac n k} [d\mid i] \sum_{j = 1} ^ {\frac m k} [d\mid j] \]由于 \(1\sim x\) 中 \(y\) 的倍数有 \(\dfrac{x}{y}\) 个，故将式子化为
\[\sum_{d = 1} ^ c \mu(d) \dfrac n {kd} \dfrac m {kd} \]整除分块即可。时间复杂度为 \(\mathcal O\left(n+T\sqrt n\right)\)。
II. SP5971 LCMSUM - LCM Sum
求：
\[\sum\limits_{i=1}^{n}\text{lcm}(i,n) \]将 \(\text{lcm}\) 化为 \(\gcd\)：
\[\begin{aligned} \sum\limits_{i = 1} ^ n \operatorname{lcm}(i, n) & = n \sum\limits_{i = 1} ^ n \frac{i}{\gcd(i, n)} \\ & = n \sum\limits_{d\mid n} \sum\limits_{i = 1} ^ n \frac{i}{d} [\gcd(i, n) = d] \\ & = n \sum\limits_{d\mid n} \sum\limits_{i = 1} ^ {\frac n d} i \left[\gcd\left(i, \frac n d\right) = 1\right] \\ & = n \sum\limits_{d\mid n} \dfrac{d \left(\varphi(d)+\epsilon(d)\right)}{2} \\ & = \dfrac n2\left(1+\sum\limits_{d \mid n}d \varphi (d)\right) \end{aligned} \]线性筛出 \(\boldsymbol 1 * (\mathrm{id} \times \varphi)\) 可以做到 \(\mathcal{O}(n + T)\)。
III. P2398 GCD SUM
求：
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\gcd\left(i,j\right) \]根据 \(\varphi *\boldsymbol 1=\text{id}\)，有
\[\begin{aligned} \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\gcd\left(i,j\right) &= \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{d\mid\gcd\left(i,j\right)}\varphi(d) \\ &= \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{d\mid i,d\mid j}\varphi(d) \\ &= \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{d=1}^{n}\varphi(d)\left[d\mid i\right]\left[d\mid j\right] \\ &= \sum\limits_{d=1}^{n}\varphi(d)\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\left[d\mid i\right]\left[d\mid j\right] \\ &= \sum\limits_{d=1}^{n}\varphi(d)\left(\dfrac{n}{d}\right)^2 \end{aligned} \]整除分块即可，时间复杂度为 \(\mathcal O\left(n + \log n\right)\)。
IV. P1390 公约数的和
求：
\[\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}\gcd\left(i,j\right) \]与 P2398 类似，去重，即去掉 \(\gcd(d,d)=d\) 和 \(\gcd(a,b)=\gcd(b,a)\)。
V. P6810 「MCOI-02」Convex Hull 凸包
求：
\[\sum\limits_{i=1}^n\sum\limits_{j=1}^m\tau(i)\tau(j)\tau(\gcd(i,j)) \]直接枚举 \(\gcd\)
\[\begin{aligned} \sum\limits_{i=1}^n\sum\limits_{j=1}^m\tau(i)\tau(j)\tau(\gcd(i,j)) &= \sum\limits_{d=1}^{\min(n,m)}\tau(d)\sum\limits_{i=1}^n\sum\limits_{j=1}^m\tau(i)\tau(j)[\gcd(i,j)=d] \\ &= \sum\limits_{d=1}^{\min(n,m)}\tau(d)\sum\limits_{i=1}^\frac nd\sum\limits_{j=1}^\frac md\tau(id)\tau(jd)[\gcd(i,j)=1] \\ &= \sum\limits_{d=1}^{\min(n,m)}\tau(d)\sum\limits_{D=1}^{\frac nd} \mu(D) \sum\limits_{i=1}^{\frac n{dD}}\sum\limits_{j=1}^{\frac n{dD}}\tau(idD)\tau(jdD) \end{aligned} \]令 \(T=dD\)
\[\sum\limits_{T=1}^{\min(n,m)}\sum\limits_{d\mid T}\tau(d)\mu\left(\dfrac{T}{d}\right)\sum\limits_{i=1}^{\frac nT}\sum\limits_{j=1}^{\frac nT}\tau(iT)\tau(jT) \]有 \(\tau * \mu =\boldsymbol 1\)
\[\sum\limits_{T=1}^{\min(n,m)}\sum\limits_{i=1}^{\frac nT}\tau(iT)\sum\limits_{j=1}^{\frac nT}\tau(jT) \]发现后面一坨式子可以用 Dirichlet 后缀和优化，只需要把 Dirichlet 前缀和倒着写就好了。
时间复杂度为 \(\mathcal O\left(\min(n,m)(\log\log n+\log\log m)\right)\)。
VI. P1447 [NOI2010] 能量采集
求：
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}(2\times\gcd(i,j)-1) \]简单转化
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}(2\times\gcd(i,j)-1)=2\times\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\gcd(i,j)-n\times m \]中间求和的式子就是 P2398 了。
VII. P2158 [SDOI2008] 仪仗队
求：
\[\sum\limits_{i=1}^{n-1}\sum\limits_{j=1}^{n-1}[\gcd(i,j)=1]+2 \]结论一，注意特判 \(n=1\) 的情况。
VIII. P3455 [POI2007]ZAP-Queries
IX. P4450 双亲数
X.P4318 完全平方数
求：\(T\) 组数据，第 \(k\) 个没有完全平方因子的数。
题目即求解 \(\min x\) 使得
\[\sum\limits_{i=1}^{x}\mu(i)^2=k \]记 \(f(x)=\sum\limits_{i=1}^{x}\mu(i)^2\)，不难发现 \(f(x)\) 单调递增。因此考虑二分。
那么问题的核心在于求解 \(f(x)\)，考虑容斥。因为对 \(\mathbb N\) 做容斥的系数为 \(\mu\)，不难得到
\[f(x)=\sum\limits_{i=1}^{i^2<n}\mu(i)\times\dfrac{n}{i^2} \]时间复杂度为 \(\mathcal O(n + T\sqrt n\log n)\)。
XI. P1829 [国家集训队] Crash的数字表格 / JZPTAB
求：
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\text{lcm}(i,j) \]将 \(\text{lcm}\) 化为 \(\gcd\)：
\[\begin{aligned} \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\text{lcm}(i,j) &= \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\dfrac{i\cdot j}{\gcd(i,j)} \\ &= \sum\limits_{d=1}^{n}d\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=d] \\ &= \sum\limits_{d=1}^{n}d\sum\limits_{i=1}^{\frac nd}\sum\limits_{j=1}^{\frac md}[\gcd(i,j)=1] \\ &= \sum\limits_{d=1}^{n}d\sum\limits_{i=1}^{\frac nd}\sum\limits_{j=1}^{\frac md}\sum\limits_{t\mid\gcd(i,j)}\mu(t) \\ \end{aligned} \]记 \(s(n)=\sum_{i=1}^ni=\frac{n(n+1)}2\)，先枚举 \(t\)
\[\sum\limits_{d=1}^{n}d\sum\limits_{t=1}^{\frac nd}t^2\mu(t)s\left(\dfrac{n}{dt}\right)s\left(\dfrac{m}{dt}\right) \]记 \(T=dt\)，先枚举 \(s\)
\[\sum\limits_{T=1}^n s\left(\dfrac nT\right)s\left(\dfrac mT\right)T\sum\limits_{d\mid T}d\mu(T) \]中间 \(s\) 的部分可以数论分块做，\(T\sum\limits_{d\mid T}d\mu(T)\) 是个积性函数可以线性筛。
时间复杂度为 \(\mathcal O(n+\sqrt n)\)。
XII. P2257 YY的GCD
求：
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^m[\gcd(i,j)\in\mathbb P] \]枚举 \(\gcd\)
\[\begin{aligned} \sum\limits_{i=1}^{n}\sum\limits_{j=1}^m[\gcd(i,j)\in\mathbb P] &= \sum\limits_{k=1}^n\sum\limits_{i=1}^{n}\sum\limits_{j=1}^m[\gcd(i,j)=k][k\in\mathbb P] \\ &= \sum\limits_{k=1}^n\sum\limits_{i=1}^{\frac nk}\sum\limits_{j=1}^{\frac mk}[\gcd(i,j)=1][k\in\mathbb P] \\ &= \sum\limits_{k=1}^n\sum\limits_{i=1}^{\frac nk}\sum\limits_{j=1}^{\frac mk}\sum\limits_{d\mid \gcd(i,j)}\mu(d)[k\in\mathbb P] \\ &= \sum\limits_{k=1}^n\sum\limits_{d=1}^{\frac nk}\mu(d)\dfrac n{kd}\dfrac m{kd}[k\in\mathbb P] \end{aligned} \]记 \(T=kd\)
\[\sum\limits_{k=1}^n\sum\limits_{d=1}^{\frac nk}\mu(d)\dfrac nT\dfrac mT[k\in\mathbb P] \]先枚举 \(T\)
\[\sum\limits_{T=1}^n\dfrac nT\dfrac mT\sum\limits_{k\mid T\land k\in\mathbb P}\mu\left(\dfrac Tk\right) \]后面那一坨式子可以预处理。具体地，对于每一个质数 \(k\)，将其所有倍数的值加上 \(\mu\left(\dfrac Tk\right)\)。
时间复杂度为 \(\mathcal O(n+T\sqrt n)\)。
XIII. P3327 [SDOI2015] 约数个数和
求：
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\tau(ij) \]技巧二，有
\[\begin{aligned} \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\tau(ij) &= \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{x\mid i}\sum\limits_{y\mid j}[\gcd(x,y)=1] \\ &= \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{x\mid i}\sum\limits_{y\mid j}\sum\limits_{d\mid \gcd(x,y)}\mu(d) \\ &= \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{x\mid i}\sum\limits_{y\mid j}\sum\limits_{d=1}^{\min(n,m)}\mu(d)[d\mid\gcd(x,y)] \\ &= \sum\limits_{d=1}^{\min(n,m)}\mu(d)\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{x\mid i}\sum\limits_{y\mid j}[d\mid\gcd(x,y)] \end{aligned} \]将枚举 \(i,j\) 的约数的贡献，每一个约数都会对它的倍数产生贡献。
\[\begin{aligned} & \sum\limits_{d=1}^{\min(n,m)}\mu(d)\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m}[d\mid\gcd(x,y)]\dfrac nx\dfrac my \\ =& \sum\limits_{d=1}^{\min(n,m)}\mu(d)\sum\limits_{x=1}^{\frac nd}\sum\limits_{y=1}^{\frac md}\dfrac n{dx}\dfrac m{dy} \\ =& \sum\limits_{d=1}^{\min(n,m)}\mu(d)\left(\sum\limits_{x=1}^{\frac nd}\frac n{dx}\right)\left(\sum\limits_{y=1}^{\frac md}\frac m{dy}\right) \end{aligned} \]括号内的东西可以整除分块预处理。时间复杂度为 \(\mathcal O(n+n\sqrt n+T\sqrt n)\)。
XIV. P3911 最小公倍数之和
求：
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^n\text{lcm}(a_i,a_j) \]记 \(c_i\) 为 \(i\) 出现的次数，则有
\[\begin{aligned} \sum\limits_{i=1}^n\sum\limits_{j=1}^n c_i\cdot c_j\cdot \text{lcm}(i,j) &= \sum\limits_{i=1}^n\sum\limits_{j=1}^n c_i\cdot c_j\cdot\dfrac{i\cdot j}{\gcd(i,j)} \\ &= \sum\limits_{k=1}^n\sum\limits_{i=1}^n\sum\limits_{j=1}^n c_i\cdot c_j\cdot\dfrac{i\cdot j}k[\gcd(i,j)=k] \\ &= \sum\limits_{k=1}^n\sum\limits_{i=1}^\frac nk\sum\limits_{j=1}^\frac nk c_{ik}\cdot c_{jk}\cdot i\cdot j\cdot k[\gcd(i,j)=1] \\ &= \sum\limits_{k=1}^n\sum\limits_{i=1}^\frac nk\sum\limits_{j=1}^\frac nk\sum\limits_{d\mid\gcd(i,j)}\mu(d)\cdot c_{ik}\cdot c_{jk}\cdot i\cdot j\cdot k \\ &= \sum\limits_{k=1}^n\sum\limits_{d=1}^\frac nk\mu(d)\cdot d^2\sum\limits_{i=1}^{\frac n{kd}}\sum\limits_{j=1}^{\frac n{kd}}c_{ikd}\cdot c_{jkd}\cdot i\cdot j\cdot k \\ &= \sum\limits_{k=1}^n\sum\limits_{kd=1}^n\mu(d)\cdot d^2\sum\limits_{i=1}^{\frac n{kd}}\sum\limits_{j=1}^{\frac n{kd}}c_{ikd}\cdot c_{jkd}\cdot i\cdot j\cdot k \\ &= \sum\limits_{T=1}T\left(\sum\limits_{d\mid T}\mu(d)\cdot d\right)\left(\sum\limits_{i=1}^\frac nTc_{iT}\cdot i\right)^2 \end{aligned} \]第一个括号可以预处理，第二个括号直接暴力计算。时间复杂度为 \(\mathcal O(n\log n)\)。
XV. P3704 [SDOI2017] 数字表格
求：
\[\prod_{i=1}^n\prod_{j=1}^m\text{fib}_{\gcd(i,j)} \]答案对 \(p=998244353\) 取模。
枚举 \(\gcd\)
\[\prod_{k=1}^n\prod_{i=1}^n\prod_{j=1}^m\text{fib}_k[\gcd(i,j)=k]\\ \prod_{k=1}^n\text{fib}_k^{\prod\limits_{i=1}^n\prod\limits_{j=1}^m[\gcd(i,j)=k]} \]指数部分易求
\[\prod_{k=1}^n\text{fib}_k^{\sum\limits_{d = 1} ^ \frac nk \mu(d) \frac n {kd} \frac m {kd}} \]记 \(T=kd\)
\[\prod\limits_{T=1}^n\left(\prod\limits_{k\mid T}\text{fib}_k^{\mu\left(\frac Tk\right)}\right)^{\frac nT\frac nT} \]括号内可以预处理。
具体地，线性筛 \(\mu\)，对于每一个 \(k\) 枚举其倍数 \(T\)，乘上 \(\text{fib}_k\) 计算到 \(T\) 的贡献中。
注意到 \(\mu\) 的取值对贡献有影响的只有 \(\{1,-1\}\)，预处理 \(\text{fib}\) 的逆元即可。
预处理复杂度为 \(\mathcal O(n\log n+n\log p)\)，整除分块复杂度为 \(\mathcal O(T\sqrt n(\log p+\log \frac nT\frac mT))\)。
标签：right,frac,入门,limits,数论,sum,mid,进门,left From： https://www.cnblogs.com/QcpyWcpyQ/p/18287065