莫比乌斯反演

通过电子科技大学ACM集训队的视频学习了莫比乌斯反演
本篇内容为学习笔记

题目引入：
给定整数N和M。求满足1<=x<=N, 1<=y<=M,且gcd(x,y)为质数的点对(x,y)的个数。
数据范围：1<=N,M<=1,000,000

目录：
1.莫比乌斯函数
2.莫比乌斯函数的线性筛
3.狄利克雷卷积介绍
4.莫比乌斯反演
5.整除分块
6.杜教筛介绍

莫比乌斯函数：

线性筛：

int prime[MAXN], prime_tot;
bool prime_tag[MAXN];
int mu[MAXN];
void pre_calc(int lim) {
    mu[1] = 1;
    for(int i = 2; i <= lim; i++) {
        if(!prime_tag[i]) {
            prime[++prime_tot] = i;
            mu[i] = -1;
        }
        for(int j = 1; j <= prime_tot; j++) {
            if(i * prime[j] > lim) break;
            prime_tag[i * prime[j] ] = true;
            if(i % prime[j] == 0) {
                    mu[i * prime[j]] = 0;
                    break;
            } else {
                    mu[i * prime[j]] = -mu[i];
            }
        }
    }
}

狄利克雷卷积介绍：
狄利克雷卷积 ：

积性函数：对于任意互质的整数a和b有性质 的函数
完全积性函数：对于任意整数a和b有性质 的函数

常见积性函数：
欧拉函数：
莫比乌斯函数：
单位函数：
不变函数：
狄利克雷卷积单位元:

基础结论：莫比乌斯函数的逆元就是不变函数

莫比乌斯反演：

解决问题：

整除分块：
请先看完：https://blog.csdn.net/beautiful_CXW/article/details/83143756
然后看下图：

杜教筛优化前缀和：
先看完杜教筛--以及积性函数的前世今生：https://blog.csdn.net/weixin_43914593/article/details/104229700
学习笔记：第一行是先枚举i，再枚举i的约数d
第二行是改变枚举顺序，即先枚举d，再枚举d的倍数i
第三行是把第二行的i进行换元，即令i'=i/d

然后再来看下图是怎么对 这个积性函数应用杜教筛求前缀和的。

代码：（这里是对 求前缀和为例）

int mu_sum[MAXN];
unordered_map<ll, int> mp;  //记录已经求到的前缀和

int mu_calc(ll n) {         
    if(n < lim) return mu_sum[n];       //先处理一小段
    if(mp.count(n)) return mp[n];

    int ret = 1;
    for(ll l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        ret -= (r - l + 1) * mu_calc(n / l);
    }
    return mp[n] = ret;
}