莫反，数竞与信竞结合的高潮。
前置
- 初中数学
草稿纸和有墨水的笔
定义
image.png 启动
在本文中，我们只讨论其一个性质：
此结论可以由迪克卷积推出
利用这个性质，我们将超飞所有 。
例题
套路
- 提：提 转化为 。
代：将 替换为：
- 换：交换求和顺序，将变量代换 提到最外层。
例题一：基础 GCD 计数 (ZAP-Queries)
数据：，。
题意：求：
推导：
提 ：
代入莫反：
换序化简：
做法：预处理 前缀和，整除分块单次 。
例题二：GCD 求和
数据：，。
题意：求：
推导：
枚举 代入例题一：
代换 ：
卷积 ：
做法：预处理 前缀和，整除分块单次 。
例题三：质数 GCD 计数 (YY的GCD)
数据：，。
题意：求（ 为质数集合）：
推导：
枚举质数 ：
代入莫反：
代换 ：
做法：设内部函数：
线性筛预处理 前缀和，整除分块单次 。
例题四：LCM 求和 (Crash的数字表格)
数据：。
题意：求：
推导：
转 并提 ：
设 ，代入莫反：
代换 ：
化简尾项：
做法：设内部积性函数：
线性筛预处理 前缀和，整除分块单次 。
例题五：约数个数和 (SDOI2015)
数据：，。
题意：求 为约数个数：
前置结论：
推导：
代入结论：
换序，先枚举 ：
莫反经典展开：
设 ：
做法：整除分块预处理 ，外层再套整除分块双重计算。