在做數(shù)論題時，往往需要進行和式變換，然后變換成我們可以處理的和式，再針對和式做篩法、整除分塊等操作。

本文將介紹一些常見的和式變換技術(shù)。

以下出現(xiàn)的概念大部分為個人總結(jié)，未必是學術(shù)界/競賽界的統(tǒng)一說法，有不嚴謹?shù)牡胤秸堈徑狻?/p>

?? 作者：Eriktse
?? 簡介：19歲，211計算機在讀，現(xiàn)役ACM銀牌選手??力爭以通俗易懂的方式講解算法！??歡迎關(guān)注我，一起交流C++/Python算法。（優(yōu)質(zhì)好文持續(xù)更新中……）??
?? 原文鏈接（閱讀原文獲得更好閱讀體驗）：https://www.eriktse.com/algorithm/1101.html

和式的基本形式

和式一般有兩種：區(qū)間枚舉型和整除枚舉型。

區(qū)間枚舉型

我們的前綴和就是一個典型的區(qū)間枚舉型和式。

假設我們有一個定義域為的函數(shù)，那么我們可以設一個前綴和函數(shù)，定義為：

求和符號中，如果沒有特殊說明，一般枚舉的都是整數(shù)，且步長為1。

整除枚舉型

約數(shù)個數(shù)是一個典型的整除枚舉型和式，我們可以容易的寫出它的表達式：

其中 表示 可以整除 ，即 是 的因子。

約數(shù)之和也是一個整除枚舉型和式，表達式如下：

和式的基本性質(zhì)

可拆分性質(zhì)

第一種拆分如下：

這是顯然的，但是基本上用不著。

第二種拆分如下：

這也是顯然的。

常數(shù)可提取

當我們的和式里面乘上了一個常數(shù)，那么這個常數(shù)是可以提出來的，由于我們討論的數(shù)域是整數(shù)域，這個一般為整數(shù)。（其實對于實數(shù)也是滿足條件的）。

整除枚舉型變換為區(qū)間枚舉型（重要）

就比如上面那個約數(shù)之和的函數(shù)：

我們知道的取值一定在，所以我們可以轉(zhuǎn)換枚舉類型，此時枚舉指標的范圍就要改變，同時加上一個布爾函數(shù)來限定。

我們稱枚舉的東西為“指標”，例如上面和式中d|n中的d，i=1中的i。

指標變換（重要）

給定一個整數(shù)，對于下面這種和式，我們可以把指標進行轉(zhuǎn)換。

現(xiàn)在令，為什么會這么想呢？因為我們后面的布爾函數(shù)中要求都包含因子，如果枚舉的不是的倍數(shù)的時候這個式子是沒有貢獻的。

所以我們可以不一個個枚舉，變?yōu)槊杜e的倍數(shù)。我們進行整體的代換：

然后變換枚舉范圍和布爾函數(shù)，注意這里的起點本應該是，但是是沒有討論意義的所以我們從開始。

現(xiàn)在我們可以發(fā)現(xiàn)后面這個布爾函數(shù)就變成了一個常見的積性函數(shù)，接下來就可以通過公式進行莫比烏斯反演（其中符號表示狄利克雷卷積）。

交換求和次序（重要）

上式進行莫比烏斯反演后可以得到如下的和式（如果不懂莫比烏斯反演可以暫時先不管，之后再學），設。

我們可以發(fā)現(xiàn)這個條件等價于，即同時是和的因子。

接下來我們進行一次枚舉類型的轉(zhuǎn)換：

接下來我們將的求和符號從后面換到前面去，因為在中沒有包含的內(nèi)容，可以直接換，這里需要自己理解一下。

轉(zhuǎn)換為整除分塊形式（十分重要）

上式轉(zhuǎn)換完成后，我們可以發(fā)現(xiàn)后面兩坨是可以進行整除分塊的。

怎么理解呢？這個式子表達的就是當確定了，在區(qū)間[1, n]中有多少整數(shù)是的倍數(shù)，顯然是個。

那么和式就可轉(zhuǎn)換為：

例題

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

閱讀題意我們可以知道題目所求為，不妨設：

接下來開始變換：

莫比烏斯反演：

注意這里，接著變換。

后面兩坨可以進行整除分塊，同時換一下的枚舉類型：

令，交換求和次序。

再交換求和次序：

現(xiàn)在發(fā)現(xiàn)后面那一塊，可以通過類似歐拉篩的方法進行預處理。

我們設一個函數(shù)：

那么的含義就是對于的每一個質(zhì)因子，將它的加到自身上。

做完了。

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]的本質(zhì)不同質(zhì)因子+1，或已經(jīng)含有平方因子
        }
    }
    
    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;
}

結(jié)束

?? 本文由eriktse原創(chuàng)，創(chuàng)作不易，如果對您有幫助，歡迎小伙伴們點贊??、收藏?、留言??