在做數論題時，往往需要進行和式變換，然后變換成我們可以處理的和式，再針對和式做篩法、整除分塊等操作，
本文將介紹一些常見的和式變換技術，
以下出現的概念大部分為個人總結，未必是學術界/競賽界的統一說法，有不嚴謹的地方請諒解，
?? 作者：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原創，創作不易，如果對您有幫助，歡迎小伙伴們點贊??、收藏?、留言??
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/548971.html
標籤：其他
上一篇：ConTeXt 蹊徑
下一篇：18.護網中的社工手段