共计 4329 个字符,预计需要花费 11 分钟才能阅读完成。
在做数论题时,往往须要进行和式变换,而后变换成咱们能够解决的和式,再针对和式做筛法、整除分块等操作。
本文将介绍一些常见的和式变换技术。
以下呈现的概念 大部分为集体总结,未必是学术界 / 比赛界的对立说法,有不谨严的中央请谅解。
🎈 作者: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
中的d
,i=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 原创,创作不易,如果对您有帮忙,欢送小伙伴们点赞👍、珍藏⭐、留言💬