關於Mobius反演

歐拉函數 \(\varphi\)

\(\varphi(n)=\)表示不超過 \(n\) 且與 \(n\) 互質的正整數的個數
\[\varphi(n)=n\cdot \prod_{i=1}^{s}(1-\frac{1}{p_i})\]
其中 \(n = {p_1}^{\alpha1} \cdot {p_2}^{\alpha2} \cdots {p_s}^{\alpha s} \cdot\) 是 \(n\) 的標準分解。
由此易見 \(\text{Euler}\) 函數是積性函數。

線性求 \(\text{Euler}\) 函數：

#define int long long
int phi[3000005];
int n=3000000;
bool mark[3000005];
int prime[1000005];
int tot;
void getphi()
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(mark[i]==false)
        {
            prime[++tot]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=tot;j++)
        {
            if(i*prime[j]>n)
            {
                break;
            }
            mark[i*prime[j]]=true;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*phi[prime[j]];
        }
    }
    for(int i=1;i<=n;i++)
    {
        phi[i]+=phi[i-1];
    }
}

\(\text{Mobius}\)函數 \(\mu(n)\)

\[ \mu(n)= \begin{cases} 1&n=1\\ 0&n\text{ 含有平方因數}\\ (-1)^k&k\text{ 為 }n\text{ 的本質不同質因數個數}\ \end{cases} \]
證明：
\[ \varepsilon(n)= \begin{cases} 1&n=1\\ 0&n\neq 1\ \end{cases} \]

其中 \(\displaystyle\varepsilon(n)=\sum_{d\mid n}\mu(d)\) 即 \(\varepsilon=\mu*1\)

設 \(\displaystyle n=\prod_{i=1}^k{p_i}^{c_i},n'=\prod_{i=1}^k p_i\)

那麼 \(\displaystyle\sum_{d\mid n}\mu(d)=\sum_{d\mid n'}\mu(d)=\sum_{i=0}^k C_k^i\cdot(-1)^k\)

根據二項式定理，易知該式子的值在 \(k=0\) 即 \(n=1\) 時值為 \(1\) 否則為 \(0\) ，這也同時證明瞭 \(\displaystyle\sum_{d\mid n}\mu(d)=[n=1]\)

#define int long long
int mu[3000005];
int n=3000000;
bool mark[3000005];
int prime[1000005];
int tot;
void getmu()
{
    mu[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(mark[i]==false)
        {
            prime[++tot]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=tot;j++)
        {
            if(i*prime[j]>n)
            {
                break;
            }
            mark[i*prime[j]]=true;
            if(i%prime[j]==0)
            {
                mu[i*prime[j]]=0;
                break;
            }
            mu[i*prime[j]]=-mu[i];
        }
    }
}

\(\text{Dirichlet}\)捲積

\(\text{ID}:\text{ID(i)=i}\)
\(\text{1}:\text{1(i)=1}\)
定義兩個數論函數的\(\text{Dirichlet}\)捲積為：
\[(f*g)(n)=\sum_{d|n}({f(d)\times g(\frac{n}{d})}) \]
性質：\(\text{Dirichlet}\)捲積滿足交換律和結合律。
單位元：\(\varepsilon\)，\(\varepsilon(n)=[n==1]\)，任何函數捲\(\varepsilon\)都為其本身.
\(1*\mu=\varepsilon\)
\(\mu * \text{ID} = \varphi\)
\(1*\text{ID}=\sigma\)

莫比烏斯反演

公式：設 \(f(n),g(n)\) 為兩個數論函數。
如果有
\[ f(n)=\sum_{d\mid n}g(d) \]
那麼有
\[ g(n)=\sum_{d\mid n}\mu(\frac{n}{d})f(d) \]
證明：
原命題等價於：已知 \(f=g*1\) ，證明 \(g=f*\mu\)
顯然： \(f*\mu=g*1*\mu= g*\varepsilon=g\) （其中 \(1*\mu=\varepsilon\) ）

同時，還有另一種\(\text{Mobius}\)反演：
如果有
\[ f(n)=\sum_{n\mid d}g(d) \]
那麼有
\[ g(n)=\sum_{n\mid d}\mu(\frac{d}{n})f(d) \]

整除分塊

當遇到形如
\[\sum_{i=1}^{n}\lfloor \frac{n}{i} \rfloor\]
的柿子時。
可以採用\(O(\sqrt {n})\)複雜度的演算法：整除分塊
易證：對於部分連續的\(i\)，\(\frac{n}{i}\)的值是相同的，考慮把它們合併計算，可以發現發現對於每一個值相同的塊，它的最後一個數是n/(n/i)。
簡略證明：\(\frac{n}{i}\)就是所求的值，設為\(x\)，那麼可證對於值\(x\)，它所在的塊的最後一個數是\(\frac{n}{x}\)。

• 證明：反證法：對於數\(\frac{n}{x}+1\)，它所在的塊的值為\(\frac{n}{\frac{n}{x}+1}\)，且\(\frac{n}{\frac{n}{x}+1}-x=\frac{x^2}{n+x}>0\)。$\therefore \(數\)\frac{n}{x}+1 \(和數\)\frac{n}{x}$不在同一個塊中。
  然後，原命題得證。

所以，易得計算原式方法。

for(int l=1,r;l<=n;l=r+1)
{
    r=n/(n/l);
    ans+=(r-l+1)*(n/l);
}

P2257 YY的GCD

設\(f(d)=\sum_{i=1}^{n}\sum_{i=1}^{m}[gcd(i,j)=d]\)，
\(F(n)=\sum_{n\mid d}f(d)=\lfloor \frac{N}{n} \rfloor \times \lfloor \frac{M}{n} \rfloor\)
由莫比烏斯反演：\(f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)\)

\(Ans=\sum_{i=1}^{n}\sum_{i=1}^{m}[gcd(i,j)=prim]\)
\(=\sum_{p\in prim}\sum_{i=1}^{n}\sum_{i=1}^{m}[gcd(i,j)=p]\)
\(=\sum_{p\in prim}f(p)\)
\(=\sum_{p\in prim}\sum_{p|d}\mu(\frac{d}{p})F(d)\)
改為枚舉\(\frac{d}{p}\)：
\(Ans=\sum_{p\in prim}\sum_{i}^{min(\lfloor \frac{n}{p} \rfloor,\lfloor \frac{m}{p} \rfloor)}\mu(i)F(dp)\)
\(=\sum_{p\in prim}\sum_{d}^{min(\lfloor \frac{n}{p} \rfloor,\lfloor \frac{m}{p} \rfloor)}\mu(d) \times \lfloor \frac{N}{dp} \rfloor \times \lfloor \frac{M}{dp} \rfloor\)
設\(dp=T,t=p\)
\(Ans=\sum_{t\in prim}\sum_{d}^{min(\lfloor \frac{n}{t} \rfloor,\lfloor \frac{m}{t} \rfloor)}\mu(\frac{T}{t}) \times \lfloor \frac{N}{T} \rfloor \times \lfloor \frac{M}{T} \rfloor\)
\(=\sum_{T=1}^{min(n,m)}\sum_{t\in prim,t|T}\mu(\frac{T}{t}) \times \lfloor \frac{N}{T} \rfloor \times \lfloor \frac{M}{T} \rfloor\)
\(=\sum_{T=1}^{min(n,m)}(\lfloor \frac{N}{T} \rfloor \times \lfloor \frac{M}{T} \rfloor) \times \sum_{t\in prim,t|T}\mu(\frac{T}{t})\)

代碼：
//sum即為\(\sum_{t\in prim,t|T}\mu(\frac{T}{t})\)的首碼和

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int prime[10000005];
int mu[10000005];
ll f[10000005];
ll sum[10000005];
bool vis[10000005];
int cnt;
void init()
{
    mu[1]=1;
    for(int i=2;i<=10000000;i++)
    {
        if(vis[i]==false)
        {
            mu[i]=-1;
            prime[++cnt]=i;
        }
        for(int j=1;j<=cnt&&i*prime[j]<=10000000;j++)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]==0)
            {
                break;
            }
            mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        for(int j=1;j*prime[i]<=10000000;j++)
        {
            f[j*prime[i]]+=mu[j];
        }
    }
    for(int i=1;i<=10000000;i++)
    {
        sum[i]=sum[i-1]+f[i];
    }
}
ll solve(int a,int b)//運用整除分塊
{
    ll ans=0;
    if(a>b)
    {
        swap(a,b);
    }
    for(int l=1,r=0;l<=a;l=r+1)
    {
        r=min(a/(a/l),b/(b/l));
        ans+=(ll)(sum[r]-sum[l-1])*(a/l)*(b/l);
    }
    return ans;
}
signed main()
{
    init();
    int T;
    cin>>T;
    for(int i=1;i<=T;i++)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        printf("%lld\n",solve(a,b));
    }
    return 0;
}