前置知識

\(1.\) 艾佛森括弧：
\([P]=\begin{cases}1 & \mathtt{(if\ P\ is \ true)}\\0 & \mathtt{(otherwise)}\end{cases}\)
\(2.\) \(a\mid b\) 表示 \(a\) 是 \(b\) 的因數
\(3.\) 整除分塊：\(\displaystyle\sum_{i=1}^n\lfloor\dfrac{N}{i}\rfloor\)
\(4.\) \(p\) 沒有特殊說明時表示質數
\(5.\) \(\mathbb{P}\) 表示質數集，\(\mathbb{Z}\) 表示整數集。
\(6.\) 常見的函數：

• 常函數：\(1(x)=1\)
• 單位元函數：\(\epsilon(x)=[x=1]\)
• 恆等函數：\(Id_k(x)=x^k\)
• 因數函數：\(d(x)=\displaystyle\sum_{i\mid x}1\)
• 因數和函數：\(\sigma(x)_k=\displaystyle\sum_{i\mid x}i^k\)
• 歐拉函數：\(\varphi(x)=\displaystyle\sum_{i=1}^x[\gcd(i,x)=1]\)

函數

數論函數

數論函數指一類定義域是正整數，值域是一個數集的函數。有：

• \((f+g)(x)=f(x)+g(x)\)
• \((x*f)(n)=x*f(n)\)

積性函數

當數論函數 \(f\) 對於 \(\gcd(n,m)=1\) 有：

則數論函數 \(f\) 為積性函數。
例如：\(d(x),\varphi(x)\)

完全積性函數

當積性函數 \(f\) 對於 \(\gcd(n,m)\not=1\) 仍有：

則積性函數 \(f\) 為完全積性函數。
例如：\(\epsilon(x),id_k(x)\)

狄利克雷捲積 (dirichlet)

定義兩個函數 \(f(n)\) 和 \(g(n)\) 的狄利克雷捲積 \((f*g)(n)\) 其中 \(*\) 為捲積符號：

同時狄利克雷捲積滿足以下一些性質：

• \(f*g=g*f\)
• \((f*g)*h=f*(g*h)\)
• \(f*h+g*h=(f+g)*h\)
• \((xf)*g=x(f*g)\)
• \(\epsilon*f=f\)
• 對於每一個 \(f(1)\not=1\) 的函數 \(f\) 都有逆元 \(g\)，使得 \(f*g=\epsilon\)

那麼對於一個 \(f(1)\not=1\) 的函數 \(f\) 的逆元 \(g\) 該如何計算呢
我們只需要通過狄利克雷捲積的定義簡單推導一下得到：

這樣就有：\(\displaystyle\sum_{i\mid n}f(i)g(\dfrac{n}{i})=f(1)g(n)+\displaystyle\sum_{i\mid n,i\not=1}=[n=1]=\epsilon\)。

歐拉函數 (Euler)

定義

歐拉函數用 \(\varphi\) 表示，定義：

解釋：\(\varphi(n)\) 表示 \(1\sim n\) 中與 \(n\) 互質的數的個數。

公式

先設 \(n=\displaystyle\prod_{i=1}^kp_i^{t_i}\)，則有：

證明：
我們先假設 \(n\in\mathbb{N^+}\) 只存在質因數 \(p,q\)。
考慮容斥，與 \(n\) 互質的數就是所有數減去 \(p,2p,\cdots,\lfloor\dfrac{n}{p}\rfloor,q,2q,\cdots,\lfloor\dfrac{n}{q}\rfloor\)。
同時根據容斥原理，需要補回 \(pq,2pq,\cdots,\lfloor\dfrac{n}{pq}\rfloor\)。
即 \(\varphi(n)=n-\dfrac{n}{p}-\dfrac{n}{q}+\dfrac{n}{pq}=n\left(1-\dfrac{1}{p}\right)\left(1-\dfrac{1}{q}\right)\)
那麼同理，當 \(n=\displaystyle\prod_{i=1}^{k}p_i^{t_i}\) 時，有：

\[\varphi(n)=n\left(1-\dfrac{1}{p_1}\right)\left(1-\dfrac{1}{p_2}\right)\cdots\left(1-\dfrac{n}{p_k}\right)=n\displaystyle\prod_{i=1}^k\left(1-\dfrac{1}{p_i}\right) \]

積性函數

函數 \(\varphi\) 滿足 \(\varphi(nm)=\varphi(n)\varphi(m)\ \ \ (\gcd(n,m)=1)\)。
即 \(\varphi\) 為積性函數。

證明：
設 \(n=\displaystyle\prod_{i=1}^kp_i^{a_i},m=\displaystyle\prod_{i=1}^tq_i^{b_i}\ \ \ (\gcd(n,m)=1)\)

\[\begin{aligned}\varphi(nm)= & nm\displaystyle\prod_{i=1}^k\left(1-\dfrac{1}{p_i}\right)\displaystyle\prod_{j=1}^t\left(1-\dfrac{1}{q_j}\right)\\= & n\displaystyle\prod_{i=1}^k\left(1-\dfrac{1}{p_i}\right)m\displaystyle\prod_{j=1}^t\left(1-\dfrac{1}{q_j}\right)\\ = & \varphi(n)\varphi(m)\end{aligned} \]

性質

證明：
記 \(f(n)=\displaystyle\sum_{d\mid n}\varphi(d)\)。則由於：
\(f(n)f(m)=\displaystyle\sum_{i\mid n}\varphi(i)\displaystyle\sum_{j\mid n}\varphi(j)=\displaystyle\sum_{d\mid nm}\varphi(d)=f(nm)\)
可以得到 \(f(n)\) 為積性函數。
設 \(n=\displaystyle\prod_{i=1}^kp_i^{t_i}\)。
而對於 \(f(p^c)=\displaystyle\sum_{i=1}^c\varphi(p^i)=\displaystyle\sum_{i=1}^cp^i-p^{i-1}=p^c\)
\(\therefore f(n)=\displaystyle\prod_{i=1}^kf(p_i^{t_i})=\displaystyle\prod_{i=1}^kp_i^{t_i}=n\)

實現

我們可以通過線性篩篩質數的時候是順便就把歐拉函數篩出來。

void Euler(int n){
    phi[1]=1;
    for (int i=2;i<=n;i++){
        if (!isp[i])primes.push_back(i),phi[i]=i-1;
        for(auto p:primes){
            if(p*i>n)break;
            isp[p*i]=1;
            if (!(i%p)){
                phi[p*i]=phi[i]*p;
                break;
            }else phi[p*i]=phi[p]*phi[i];
        }
    }
}

莫比烏斯函數 (Möbius)

定義

莫比烏斯函數用 \(\mu\) 表示，定義：

解釋一下對 \(\mu(x)\) 的定義：

• 當 \(x=1\) 時，\(\mu(x)=1\)；
• 當 \(x\) 含有任何的質因數的冪次 \(\ge 2\)，\(\mu(x)=0\)；
• 當 \(x=\displaystyle\prod_{i=1}^kp_i\)，且所有 \(p_i\) 的互不相同時，\(\mu(x)=(-1)^k\)

性質

只知道莫比烏斯函數的定義還遠遠不夠，我們還需要瞭解一下他的性質：

• \(n\in\mathbb{N^+},\displaystyle\sum_{d\mid n}\mu(d)=[n=1],\mu*1=\epsilon\)。

證明：

當 \(n=1\) 時，\(\displaystyle\sum_{d|n}=\mu(1)=1=[n=1]\)。

當 \(n>1\) 時，我們記 \(n=\displaystyle\prod_{i=1}^kp_i^{t_i}\)
當 \(\exists t_i,t_i>1\) 時，\(\mu(n)=0\)。
當 \(\forall t_i,t_i=1\) 時，對於 \(\mu(d)=(-1)^r\) 這樣的存在 \(C_k^r\) 個。
\(\therefore \displaystyle\sum_{d\mid n}\mu(d)=C_k^0+C_k^1+C_k^2+\cdots+(-1)^kC_k^k=\displaystyle\sum_{i=0}^k(-1)^iC_k^i\)
由二項式定理：\((x+y)^n=\displaystyle\sum_{i=0}^nC_n^ix^iy^{n-i}\)
\(\therefore \displaystyle\sum_{d\mid n}\mu(d)=\displaystyle\sum_{i=0}^k(-1)^iC_k^i=(-1+1)^n=0\)

• \(\displaystyle\sum_{d\mid n}\dfrac{\mu(d)}{d}=\dfrac{\varphi(n)}{n}\)

證明：
\(\begin{aligned}\displaystyle\sum_{d\mid n}\dfrac{\mu(d)}{d}=&\displaystyle\sum_{d\mid n}\dfrac{\mu(d)\frac{n}{d}}{n}\\=& \dfrac{\displaystyle\sum_{d\mid n}\mu(d)Id\left(\frac{n}{d}\right)}{n}\\= & \dfrac{\mu(n)*Id(n)}{n}\end{aligned}\)
根據 \(\varphi*1=Id\Leftrightarrow\varphi*1*\mu=\mu*Id\Leftrightarrow\varphi*\epsilon=\mu*Id\) 得
\(\displaystyle\sum_{d\mid n}\dfrac{\mu(d)}{d}=\dfrac{\mu(n)*Id(n)}{n}=\dfrac{\varphi(n)}{n}\)

實現

和歐拉函數一樣，也可以在篩質數的時候順便得到。

void getMu(int n){
    mu[1]=1;
	isp[0]=isp[1]=1;
    for(int i=2;i<=n;++i){
        if(!isp[i])mu[p[++cnt]=i]=-1;
        for(int j=1;j<=cnt&&p[j]*i<=n;++j){
            isp[i*p[j]]=1;
            if(!(i%p[j]))break;
            else mu[p[j]*i]=-mu[i];
        }
    }
}

莫比烏斯反演

當存在有兩個函數 \(f\) 和 \(g\) 滿足：\(f(n)=\displaystyle\sum_{d|n}g(d)\) 即 \(f=g*1\)。
則一定有：

證明：

\[f=g*1\Leftrightarrow f*\mu=g*1*\mu \Leftrightarrow f*\mu=g \]

倍數形式：

例題

\(1.\) P2522 Problem B
求 \(\displaystyle\sum_{i=a}^b\displaystyle\sum_{j=c}^d[\gcd(i,j)=k]\)

設 \(f(k)=\displaystyle\sum_{i=1}^n\displaystyle\sum_{j=1}^m[\gcd(i,j)=k],g(n)=\displaystyle\sum_{n\mid k}f(k)\)
則通過莫比烏斯反演的倍數形式可以得到： \(f(x)=\displaystyle\sum_{x\mid k}\mu(\lfloor\dfrac{k}{x}\rfloor)g(k)\)
我們在考慮對於函數 \(g\) 的處理：
\(\begin{aligned}g(x)=&\displaystyle\sum_{x\mid k}\displaystyle\sum_{i=1}^n\displaystyle\sum_{j=1}^m[\gcd(i,j)=k]\\=&\displaystyle\sum_{i=1}^n\displaystyle\sum_{j=1}^m[x\mid \gcd(i,j)]\\=&\displaystyle\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}\displaystyle\sum_{j=1}^{\lfloor\frac{m}{x}\rfloor}[1\mid \gcd(i,j)]\\=&\lfloor\dfrac{n}{x}\rfloor\lfloor\dfrac{m}{x}\rfloor\end{aligned}\)
我們在將函數 \(g\) 帶回函數 \(f\)，同時枚舉 \(\lfloor\dfrac{k}{x}\rfloor\) 記為 \(t\)：
\(f(x)=\displaystyle\sum_{t=1}^{\min(n,m)}\mu(t)\lfloor\dfrac{n}{tx}\rfloor\lfloor\dfrac{m}{tx}\rfloor\)
那麼對於最後的答案我們只需要一個簡單的容斥：
\(ans=\displaystyle\sum_{i=1}^b\displaystyle\sum_{j=1}^d[\gcd(i,j)=k]-\displaystyle\sum_{i=1}^{a-1}\displaystyle\sum_{j=1}^d[\gcd(i,j)=k]-\displaystyle\sum_{i=1}^b\displaystyle\sum_{j=1}^{c-1}[\gcd(i,j)=k]+\displaystyle\sum_{i=1}^{a-1}\displaystyle\sum_{j=1}^{c-1}[\gcd(i,j)=k]\)
通過上的函數 \(f,g\) 帶入即可，通過整除分塊可以得到時間複雜度 \(O(\sqrt{n})\)。