【数论】莫反&欧反 学习笔记
GIFBMP
·
·
个人记录
一、积性函数
对于任意的 i,j ，满足 \gcd(i,j)=1，都有 f(i)f(j)=f(ij)，那么数论函数 f 被称为积性函数。
特别地，对于任意的 i,j，都有 f(i)f(j)，那么数论函数 f 被称为完全积性函数。
几个常见的积性函数：
1(n)=1
\varepsilon(n)=[n=1]
id(n)=n
\varphi(n)=\sum_{i=1}^n[\gcd(i,n)=1]
（关于 \mu，由于定义较复杂，放到下面讲）
二、狄利克雷卷积
狄利克雷卷积就是下面这个式子：
(f*g)(n)=\sum_{d|n}f(d)g({\frac{n}{d})}
有几个重要的卷积关系：
\varphi*1=id
\mu*1=\varepsilon
id*\mu=\varphi
三、整除分块
求：
\sum_{i=1}^{n}\left\lfloor\dfrac{n}{i}\right\rfloor
我们发现，很多 \left\lfloor\dfrac{n}{i}\right\rfloor 是相等的，并且只有 \sqrt{n} 种取值。
所以可以把所有相同的 \left\lfloor\dfrac{n}{i}\right\rfloor 分成一块，就可以 \Theta (\sqrt{n}) 求出了。
for (int l = 1 , r ; l <= n ; l = r + 1) {
r = n / (n / l) ;
ans += 1LL * (n / l) * (r - l + 1) ;
}
四、欧拉反演
核心公式就是上面的 \varphi *1=id。
展开来看：
\sum_{d|n}\varphi(d)=n
原理就是把原式中的 n 强行替换成上面的形式。
举个例子，求：
\sum_{i=1}^n\gcd(i,n)
毒瘤出题人把数据范围开到了 5\times10^6，卡掉了您的暴力。
于是开始推式子：
\sum_{i=1}^n\gcd(i,n)
=\sum_{i=1}^n\sum_{d|\gcd(i,n)}\varphi(d)
=\sum_{i=1}^n\sum_{d|i}\sum_{d|n}\varphi(d)
=\sum_{d|n}\sum_{i=1}^n\sum_{d|i}\varphi(d)
显然地，后面只有 \dfrac{n}{d} 个数会产生贡献，所以，原式
\sum_{d|n}\dfrac{n}{d}\varphi(d)
时间复杂度降到了 \Theta(n+\sqrt{n})，可以通过。
五、莫比乌斯反演
最常用的反演了。
先介绍下 \mu 函数：
当 $n$ **恰好**为 $m$ 个**互不相同**的质数的乘积时，$\mu(n)=(-1)^m$；
否则 $\mu(n)=0$。
核心公式就是上面讲到的 $\mu*1=\varepsilon$。
例题：P1447
题意简述：
求：
$$\sum_{i=1}^n\sum_{j=1}^m2\gcd(i,j)-1$$
我们拆一下式子，可以得到：
$$2\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)-nm$$
于是我们只要讨论中间的部分就行了。
可以得到，原式：
$$=\sum_{d=1}^nd\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}[\gcd(i,j)=1]$$
然后上套路：
$$=\sum_{d=1}^nd\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}\sum_{k|\gcd(i,j)}\mu(k)$$
$$=\sum_{d=1}^nd\sum_{k=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu(k){\left\lfloor\frac{n}{kd}\right\rfloor}{\left\lfloor\frac{m}{kd}\right\rfloor}$$
我们设 $kd=q$，替换枚举贡献，则有：
$$=\sum_{q=1}^n\sum_{d|n}d\times\mu(\dfrac{q}{d}){\left\lfloor\frac{n}{q}\right\rfloor}{\left\lfloor\frac{m}{q}\right\rfloor}$$
将 $\mu*id=\varphi$ 代入，得：
$$=\sum_{q=1}^n\varphi(q){\left\lfloor\frac{n}{q}\right\rfloor}{\left\lfloor\frac{m}{q}\right\rfloor}$$
$\Theta(n+\sqrt{n})$，可以通过本题。
Code:
```cpp
#include <cstdio>
using namespace std ;
const int MAXN = 1e5 + 10 ;
int p[MAXN] , cnt , phi[MAXN] ;
long long sum[MAXN] ;
bool isnp[MAXN] ;
int min (int a , int b) {
return a < b ? a : b ;
}
void xxs () {
phi[1] = sum[1] = 1 ;
for (int i = 2 ; i <= 1e5 ; i++) {
if (!isnp[i]) {
p[++cnt] = i ;
phi[i] = i - 1 ;
}
for (int j = 1 ; j <= cnt && i * p[j] <= 1e5 ; j++) {
isnp[i * p[j]] = 1 ;
if (i % p[j] == 0) {
phi[i * p[j]] = phi[i] * p[j] ;
break ;
}
phi[i * p[j]] = phi[i] * phi[p[j]] ;
}
sum[i] = sum[i - 1] + 1LL * phi[i] ;
}
}
int main () {
xxs () ;
int n , m ;
long long ans = 0 ;
scanf ("%d %d" , &n , &m) ;
for (int l = 1 , r ; l <= min (n , m) ; l = r + 1) {
r = min (n / (n / l) , m / (m / l)) ;
ans += 1LL * (n / l) * (m / l) * (sum[r] - sum[l - 1]) ;
}
ans = 2 * ans - 1LL * n * m ;
printf ("%lld\n" , ans) ;
return 0 ;
}
```