[ACM数论]和式变换技术,也许是最好的讲解之一

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

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

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

和式的基本形式

区间枚举型和整除枚举型。

区间枚举型

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

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

整除枚举型

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

其中 $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}ka_i = k\sum_{i=1}^{n}a_i$$

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

$$g(i = \sum_{d|n}d = \sum_{i=1}^{n}[d|n]$$

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

指标变换（重要）

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

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

{n}\sum_{j'k=1}[gcd(i'k, j'k = k]$$

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

交换求和次序（重要）

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

{m}\sum_{j=1}\sum_{d|gcd(i, j}\mu(d$$

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

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

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

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

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

那么和式就可转换为：

例题

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

$$ans=\sum_{i=1}^{{n}\sum_{j=1}}[gcd(i,j\in prim]$$

$$\sum_{i=1}^{{n}\sum_{j=1}}\sum_{p\in prim}[gcd(i,j=p]$$

{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}\rfloor}[gcd(i,j=1]$$

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

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

{\lfloor\frac{n}{p}\rfloor}\mu(d\sum_{i=1}\rfloor}[d|i]\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}[d|j]$$

$$\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$$

$$\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}}[p\in prim][p|T]\mu(\frac{T}{p}$$

我们设一个函数：

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

Code：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e7 + 9;

int sum[N], mu[N];

void init(int n = N - 2
{
	bitset<N> 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] == 0break;//此时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; ++ isum[i] += sum[i - 1];
	
}

void solve(
{
	int n, m;scanf("%lld %lld", &n, &m;
	if(n > mswap(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原创，创作不易，如果对您有帮助，欢迎小伙伴们点赞👍、收藏⭐、留言💬

编程笔记 » [ACM数论]和式变换技术,也许是最好的讲解之一