s洛谷网校SX2数论
一 知识整理
1 取整函数的性质
1.1对于正整数n，1到n中d的倍数有$\lfloor\frac n d\rfloor$个
显而易见
1.2对于任意x与正整数a,b$\lfloor\frac {\lfloor\frac x b\rfloor} a\rfloor=\lfloor\frac x {ab}\rfloor$
依然十分显然 考虑x/b的余数 显然的再被ab除时必不是整数
1.3对于任意正整数n，考虑考虑当 1 ≤ d ≤ n 时，⌊n/d⌋ 的不同的取值个数
若 d ≤ √n，则能得到的 ⌊n/d⌋ 只有不超过 √n 种。
若 d > √n，则 ⌊n/d⌋ ≤ n/d < √ n，又因为 ⌊n/d⌋ 是正整数，故此时 可能的取值也不超过 √n种
1.4
2 积性函数
2.1若对于正整数a,b且a|b都有f(ab)=f(a)f(b)则称f为积性函数
2.2显然的
若 f 是积性函数，且n的标准分解
$$
n=p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}…
$$
则
$$
f(n)=f(p_1^{\alpha_1})f(p_2^{\alpha_2})f(p_3^{\alpha_3})…
$$
2.3若要对 1 到 n 之间的所有数求出 f，注意到 Euler 筛法的过 程中可以求出每个数的最小素因子和最小素因子的幂次，利用此 就能在线性时间内计算出所需的 f 的值。
2.4
3 迪利克雷卷积
3.1定义单位函数
$$
\epsilon(x)=[x=1]
$$
易见单位函数是积性函数
3.2定义除数函数
$$
\sigma_k(n)=\sum_{d|n}d^k
$$
约数个数$\sigma_0$常记作d 约数和常记作 $\sigma_1$常记作$\sigma$
易见所有除数函数均为积性函数 显然利用普通卷积可证得
3.3欧拉函数$\varphi(x)$表示小于x且与x互质的数的个数
显然当x为素数时 $\varphi(x)=x-1$
利用容斥原理 发现
$$
\begin{align}
\varphi(x)&=x-\sum_{p_i}[\frac x {p_i}]+\sum_{p_i,p_j}[\frac x {p_ip_j}]-\sum_{p_i,p_j,p_k}[\frac x {p_ip_jp_k}]…
\
&=x(1-\sum_{p_i}[\frac 1 {p_i}]+\sum_{p_i,p_j}[\frac 1 {p_ip_j}]-\sum_{p_i,p_j,p_k}[\frac 1 {p_ip_jp_k}]…)
\
&=x(1-\frac 1 p_i)(1-\frac 1 p_j)(1-\frac 1 p_k)…
\end{align}
$$
发现该显式表达指出了欧拉函数具有积性
一个性质：
对于任意n
$$
n=\sum_{n|d}\varphi(\frac n d)=\sum_{n|d}\varphi(d)
$$
证明：
若$gcd(n,i)=d$ 则$gcd(\frac n d,\frac i d)=1$ 故这样的i有$\varphi(\frac n d)$ 个
考虑所有n|d就考虑了所有小于等于n的整数
故得证
3.3Dirichlet 卷积
定义两个数论函数f,g 的Dirichlet卷积为h
$$
h(n)=\sum_{d|n}f(d)g(\frac n d)
$$
计作h=f*g
3.4定义幂函数$Id_k(x)=x^k$
一般将$Id_1计作Id$
3.5莫比乌斯函数
$$
\mu(n)=\begin{cases}1 ,&(n=1) \(-1)^s ,&n=p_1…p_s& \0 &others\end{cases}
$$
$p_1…p_s$是不同素数
可以看出，µ(n) 恰在 n 无平方因子时非零。
易见 µ 是积性函数。
3.6可用迪利克雷卷积表示的函数关系
3.6.1$\epsilon_k=1*Id_k$ 显然
3.6.2$Id=1*\varphi$ 已证明
3.6.3$\epsilon=1*\mu$
证明：n=1时显然成立
对于n>1 设n有s个素因子 由于莫比乌斯函数
只在d无平方因子时不为零 故只需考虑d中各素因子次数为0或1的情形
故
$$
\sum_{d|n}\mu(d)=\sum^s_{k=0}(-1)^k\binom s k=(1-1)^s=0
$$
得证
4.莫比乌斯变换
4.1 若f是数论函数 $g=f*1$ 则称g是f的莫比乌斯变换 f是g的莫比乌斯逆变换
4.2 $f=g\mu \Leftrightarrow g=f1$
证明
$f=f\epsilon=f1\mu=g\mu$
十分显然
4.3利用 Dirichlet 卷积可以解决一系列求和问题。常见做法是使用 一个 Dirichlet 卷积替 换求和式中的一部分，然后调换求和顺序， 最终降低时间复杂度。
二 一些例题
1 公约数的和
对于这类题的一个想法是枚举gcd的值 因为发现
$gcd(n,m)=d\Leftrightarrow gcd(\frac n d,\frac m d)=1$
这样对于枚举上界相等的情形 就可以使用欧拉函数草过去
对于枚举上界不等的情形 就可以使用$\epsilon$函数判$1$日过去
回到本题 我们枚举gcd的值然后直接计数$\varphi(\frac n d)$再乘回d
2 longge的问题
发现符合上述套路
我们直接$\frac n d$的求欧拉函数即可 然而发现此时欧拉函数并不被连续使用
可以依据封闭形式直接计算
3 YY 的 GCD
依然适用上述套路
发现单位函数可作艾弗森约定只用 若等值不为1 运用除法即可
$$
\begin{align}
\sum^n_x\sum^m_y\epsilon(gcd(x,y))&=\sum^n_x\sum^m_y1*\mu(gcd(x,y))
\
&=\sum^n_x\sum^m_y\sum_{d|gcd(x,y)}\mu(d)
\
&=\sum_d^{min(n,m)}\sum^n_{d|x}\sum^m_{d|y}\mu(d)
\
&=\sum_d^{min(x,m)}\mu(d)[\frac n d][\frac m d]
\end{align}
$$
回到原题
$$
\begin{align}
\sum_p\sum^n_{x=1}\sum^m_{y=1}[gcd(x,y)=p]=&\sum_p\sum^{\frac n p}{x=1}\sum^{\frac m p}{y=1}\epsilon(gcd(x,y))
\
=&\sum_p\sum^{\frac n p}{x=1}\sum^{\frac m p}{y=1}\sum_{d|gcd(x,y)}\mu(d)
\
=&\sum_p\sum_d\mu(d)[\frac n {pd}][\frac m {pd}]
\
=&\sum_t^{min(n,m)}[\frac n t][\frac m t]\sum_{p|d}\mu(\frac p d)
\end{align}
$$
