【ACM数论】和式变换技术，也许是最好的讲解之一

在做数论题时，往往需要进行和式变换，然后变换成我们可以处理的和式，再针对和式做筛法、整除分块等操作。

本文将介绍一些常见的和式变换技术。

以下出现的概念大部分为个人总结，未必是学术界/竞赛界的统一说法，有不严谨的地方请谅解。

🎈 作者：Eriktse
🎈 简介：19岁，211计算机在读，现役ACM银牌选手🏆力争以通俗易懂的方式讲解算法！❤️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中……）🚀
🎈 原文链接（阅读原文获得更好阅读体验）：https://www.eriktse.com/algorithm/1101.html

和式的基本形式

和式一般有两种：区间枚举型和整除枚举型。

区间枚举型

我们的前缀和就是一个典型的区间枚举型和式。

假设我们有一个定义域为$x\in [1,n],x\in Z^{+}$的函数$f(x)$，那么我们可以设一个前缀和函数$F(x)$，定义为：

$$F(x)=\sum _{i=1}^{x}f(i)=f(1)+f(2)+...+fx()$$

求和符号中，如果没有特殊说明，一般枚举的都是整数，且步长为1。

整除枚举型

约数个数是一个典型的整除枚举型和式，我们可以容易的写出它的表达式：

$$f(n)=\sum _{d|n}1$$

其中 $d|n$ 表示 $i$ 可以整除 $n$ ，即 $i$ 是 $n$ 的因子。

约数之和也是一个整除枚举型和式，表达式如下：

$$g(n)=\sum _{d|n}d$$

和式的基本性质

可拆分性质

第一种拆分如下：

$$\sum _{i=1}^n{a}_i=\sum _{i=1}^m{a}_i+\sum _{i=m+1}^n{a}_i$$

这是显然的，但是基本上用不着。

第二种拆分如下：

$$\sum _{i=1}^n(a_i+b_i)=\sum _{i=1}^n{a}_i+\sum _{i=1}^n{b}_i$$

这也是显然的。

常数可提取

当我们的和式里面乘上了一个常数$k$，那么这个常数是可以提出来的，由于我们讨论的数域是整数域，这个$k$一般为整数。（其实对于实数也是满足条件的）。

$$\sum _{i=1}^{n}k{a}_i=k\sum _{i=1}^n{a}_i$$

整除枚举型变换为区间枚举型（重要）

就比如上面那个约数之和的函数：

$$g(i)=\sum _{d|n}d=\sum _{i=1}^n[d|n]$$

我们知道$d$的取值一定在$[1,n]$，所以我们可以转换枚举类型，此时枚举指标的范围就要改变，同时加上一个布尔函数来限定。

我们称枚举的东西为“指标”，例如上面和式中d|n中的d，i=1中的i。

指标变换（重要）

给定一个整数$k$，对于下面这种和式，我们可以把指标进行转换。

$$\sum _{i=1}^n\sum _{j=1}^n[gcd(i,j)=k]$$

现在令$i=i^{\prime }k,j=j^{\prime }k$，为什么会这么想呢？因为我们后面的布尔函数中要求$i,j$都包含因子$k$，如果枚举的$i,j$不是$k$的倍数的时候这个式子是没有贡献的。

所以我们可以不一个个枚举$i,j$，变为枚举$k$的倍数。我们进行整体的代换：

$$\sum _{i^{\prime }k=1}^n\sum _{j^{\prime }k=1}^n[gcd(i^{\prime }k,j^{\prime }k)=k]$$

然后变换枚举范围和布尔函数，注意这里$i$的起点本应该是$\lfloor \frac{1}{k}\rfloor$，但是$0$是没有讨论意义的所以我们从$1$开始。

$$\sum _{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{j=1}^{\lfloor \frac{n}{k}\rfloor }[gcd(i,j)=1]$$

现在我们可以发现后面这个布尔函数就变成了一个常见的积性函数$ϵ$，接下来就可以通过公式$\mu \ast I=ϵ$进行莫比乌斯反演（其中符号$\ast$表示狄利克雷卷积）。

交换求和次序（重要）

上式进行莫比乌斯反演后可以得到如下的和式（如果不懂莫比乌斯反演可以暂时先不管，之后再学），设$m=\lfloor \frac{n}{k}\rfloor$。

$$\sum _{i=1}^m\sum _{j=1}^m\sum _{d|gcd(i,j)}\mu (d)$$

我们可以发现$d|gcd(i,j)$这个条件等价于$[d|i][d|j]$，即$d$同时是$i$和$j$的因子。

接下来我们进行一次枚举类型的转换：

$$\sum _{i=1}^m\sum _{j=1}^m\sum _{d=1}^m[d|i][d|j]\mu (d)$$

接下来我们将$d$的求和符号从后面换到前面去，因为在$\mu (d)$中没有包含$i,j$的内容，可以直接换，这里需要自己理解一下。

$$su{m}_{d=1}^m\mu (d)\sum _{i=1}^m[d|i]\sum _{j=1}^m[d|j]$$

转换为整除分块形式（十分重要）

上式转换完成后，我们可以发现后面两坨是可以进行整除分块的。

$$\sum _{i=1}^m[d|i]=\lfloor \frac{m}{d}\rfloor$$

怎么理解呢？这个式子表达的就是当$d$确定了，在区间[1, n]中有多少整数是$d$的倍数，显然是$\lfloor \frac{m}{d}\rfloor$个。

那么和式就可转换为：

$$\sum _{i=1}^m\lfloor \frac{m}{d}\rfloor \lfloor \frac{m}{d}\rfloor$$

例题

luogu P2257 YY的GCD：https://www.luogu.com.cn/problem/P2257

阅读题意我们可以知道题目所求为，不妨设$n\le m$：

$$ans=\sum _{i=1}^n\sum _{j=1}^m[gcd(i,j)\in prim]$$

接下来开始变换：

$$\sum _{i=1}^n\sum _{j=1}^m\sum _{p\in prim}[gcd(i,j)=p]$$

$$\sum _{p\in prim}\sum _{i=1}^{\lfloor \frac{n}{p}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{p}\rfloor }[gcd(i,j)=1]$$

莫比乌斯反演：

$$\sum _{p\in prim}\sum _{i=1}^{\lfloor \frac{n}{p}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{p}\rfloor }\sum _{d|gcd(i,j)}\mu (d)$$

注意这里$n\le m$，接着变换。

$$\sum _{p\in prim}\sum _{i=1}^{\lfloor \frac{n}{p}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{p}\rfloor }\sum _{d=1}^{\lfloor \frac{n}{p}\rfloor }[d|i][d|j]\mu (d)$$

$$\sum _{p\in prim}\sum _{d=1}^{\lfloor \frac{n}{p}\rfloor }\mu (d)\sum _{i=1}^{\lfloor \frac{n}{p}\rfloor }[d|i]\sum _{j=1}^{\lfloor \frac{m}{p}\rfloor }[d|j]$$

后面两坨可以进行整除分块，同时换一下$p$的枚举类型：

$$\sum _{p=1}^n[p\in prim]\sum _{d=1}^{\lfloor \frac{n}{p}\rfloor }\mu (d)\lfloor \frac{n}{pd}\rfloor \lfloor \frac{m}{pd}\rfloor$$

令$T=pd$，交换求和次序。

$$\sum _{p=1}^n[p\in prim][p|T]\sum _{T=1}^n\mu (\frac{T}{p})\lfloor \frac{n}{T}\rfloor \lfloor \frac{m}{T}\rfloor$$

再交换求和次序：

$$\sum _{T=1}^n\lfloor \frac{n}{T}\rfloor \lfloor \frac{m}{T}\rfloor \sum _{p=1}^n[p\in prim][p|T]\mu (\frac{T}{p})$$

现在发现$p$后面那一块，可以通过类似欧拉筛的方法进行预处理。

我们设一个函数：

$$F(T)=\sum _{p=1}^n[p\in prim][p|T]\mu (\frac{T}{p})$$

那么$F(T)$的含义就是对于$T$的每一个质因子$p$，将它的$\mu (\frac{T}{p})$加到自身上。

做完了。

Code：

#include 
#define int long long
using namespace std;
const int N = 1e7 + 9;

int sum[N], mu[N];

void init(int n = N - 2)
{
	bitset vis;
	vector<int> prim;
	vis[1] = true;
	mu[1] = 1;
	
	for(int i = 2;i <= n; ++ i)
	{
		if(!vis[i])prim.push_back(i), mu[i] = -1;
		
		for(int j = 0;j < prim.size() and i * prim[j] <= n; ++ j)
		{
			vis[i * prim[j]] = true;
			if(i % prim[j] == 0)break;//此时i * prim[j]含有平方因子
			
			mu[i * prim[j]] = -mu[i];//此时i * prim[j]的本质不同质因子+1，或已经含有平方因子
		}
	}
	
	for(int i = 0;i < prim.size(); ++ i)
	{
		for(int j = 1; prim[i] * j  <= n; ++ j)
		{
			sum[prim[i] * j] += mu[j];
		}
	}
	
	for(int i = 1;i <= n; ++ i)sum[i] += sum[i - 1];
	
}

void solve()
{
	int n, m;scanf("%lld %lld", &n, &m);
	if(n > m)swap(n, m);
	int ans = 0;
	for(int l = 1, r;l <= n; l = r + 1)
	{
		r = min(n / (n / l), m / (m / l));
		ans += (sum[r] - sum[l - 1]) * (n / l) * (m / l);
	}
	printf("%lld\n", ans);
}

signed main()
{
	init();
	int _;scanf("%lld", &_);
	while(_ --)solve();
	return 0;
}

结束

🎈 本文由eriktse原创，创作不易，如果对您有帮助，欢迎小伙伴们点赞👍、收藏⭐、留言💬