【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}ka_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中的di=1中的i

指标变换(重要)

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

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

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

所以我们可以不一个个枚举\(i, j\),变为枚举\(k\)的倍数。我们进行整体的代换:

\[\sum_{i'k = 1}^{n}\sum_{j'k=1}^{n}[gcd(i'k, j'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]
\]

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

交换求和次序(重要)

上式进行莫比乌斯反演后可以得到如下的和式(如果不懂莫比乌斯反演可以暂时先不管,之后再学),设\(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\)的内容,可以直接换,这里需要自己理解一下。

\[\\sum_{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 <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] == 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原创,创作不易,如果对您有帮助,欢迎小伙伴们点赞?、收藏⭐、留言?

原文链接:https://www.cnblogs.com/eriktse/p/17280451.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:【ACM数论】和式变换技术,也许是最好的讲解之一 - Python技术站

(0)
上一篇 2023年4月17日
下一篇 2023年4月17日

相关文章

  • python算法与数据结构之单链表的实现代码

    下面是详细讲解“Python算法与数据结构之单链表的实现代码”的完整攻略,包括节点类的定义、链表类的定义、节点的插入、删除和查找等操作,以及两个示例说明。 节点类的定义 节点类表示单链表的节点,包括节点值和下一个节点指针。以下是Python实现节点类的示例代码: class ListNode: def __init__(self, val=0, next=N…

    python 2023年5月14日
    00
  • C++ 数据结构二叉树(前序/中序/后序递归、非递归遍历)

    下面是关于C++二叉树数据结构的详细攻略。 什么是二叉树 二叉树是一种树形数据结构,每个节点最多有两个子节点:左节点和右节点。一个节点没有左节点或右节点则分别为左子树和右子树为空。 递归遍历二叉树 前序遍历 前序遍历是指对于一棵二叉树,在访问右子树之前,先访问根节点,然后访问左子树。 下面是C++递归遍历二叉树的前序遍历示例代码: template <…

    数据结构 2023年5月17日
    00
  • 数据结构TypeScript之二叉查找树实现详解

    数据结构TypeScript之二叉查找树实现详解 什么是二叉查找树 二叉查找树(Binary Search Tree,简称BST)是一种基础的数据结构,也是一种常用的搜索算法。它通过以二叉树的形式表示各个结点之间的关系,实现了快速查找、添加、删除等操作。对于任何一个节点,其左子树上的节点值均小于该节点的值,右子树上的节点值均大于该节点的值。 二叉查找树的实现…

    数据结构 2023年5月17日
    00
  • 浅谈PHP链表数据结构(单链表)

    介绍 链表是一种常见的数据结构,它包括单链表和双链表,本文中我们将会介绍PHP的单链表数据结构实现,具体而言我们将会实现一个包括插入节点,删除节点,打印节点等基本操作的单链表,帮助读者深入理解PHP链表数据结构。 创建节点 链表数据结构是由一个个节点组成的,我们首先要实现一个节点的创建函数,这个函数接受两个参数,一个是节点数据,另一个是下一个节点的指针地址。…

    数据结构 2023年5月17日
    00
  • C++ 数据结构之kmp算法中的求Next()函数的算法

    C++ 数据结构之kmp算法中的求Next()函数的算法 什么是KMP算法和Next()函数 KMP算法(Knuth-Morris-Pratt算法)是一种字符串匹配算法,能够解决的问题是,在一个文本串S中查找一个模式串P是否出现并且返回第一次出现的位置。而Next()函数则是在KMP算法中使用的一个关键的子函数,用于计算模式串P中每个前缀的最长相同真前缀和后…

    数据结构 2023年5月17日
    00
  • Java数据结构之线段树的原理与实现

    Java数据结构之线段树的原理与实现 什么是线段树 线段树是一种基于分治思想的数据结构,它可以用来解决各种区间查询问题,例如区间求和、最大值、最小值等等。在算法竞赛和数据结构课程中,线段树被广泛应用,是一种非常实用的数据结构。 线段树的基本原理 线段树是一种二叉树,它的每个节点包含一个区间,叶子节点表示区间中的单个元素,非叶子节点表示区间的合并。 线段树的建…

    数据结构 2023年5月17日
    00
  • python实现梯度法 python最速下降法

    下面是详细讲解“Python实现梯度法和最速下降法”的完整攻略。 梯度法 梯度法是一种常用的优化算法用于求解无约束优化问题。其基本思想是每一步代中,沿着当前的梯度方向进行下降,以望找到函数的最小值点。 下面是一个Python实现梯度法的示例: import numpy as np def gradient_descent(f, df, x0, alpha=0…

    python 2023年5月14日
    00
  • c语言数据结构之并查集 总结

    C语言数据结构之并查集总结 简介 并查集,也称作不相交集合,是一种树型的数据结构。并查集用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。 并查集只有两个操作: find:确定某个元素属于哪个子集。它可以被用来确定两个元素是否属于同一子集。 union:将两个子集合并成同一个集合。 基本实现 以快速查找find和…

    数据结构 2023年5月17日
    00
合作推广
合作推广
分享本页
返回顶部