莫比乌斯反演学习笔记

余数求和

对于任意整数 $x\in[1,n]$ 设 $g(x)=\lfloor\frac{k}{\lfloor\frac{k}{x}\rfloor}\rfloor$

$\because f(x)=\frac{k}{x}$ 单调递减

又 $(x)=\lfloor\frac{k}{\lfloor\frac{k}{x}\rfloor}\rfloor\geq\lfloor\frac{k}{(\frac{k}{x})}\rfloor=x$

$\therefore \lfloor\frac{k}{g(x)}\rfloor\leq\lfloor\frac{k}{x}\rfloor$

$\because \lfloor\frac{k}{g(x)}\rfloor\geq\lfloor\frac{k}{(\frac{k}{\lfloor\frac{k}{x}\rfloor})}\rfloor=\lfloor\frac{k}{k}\lfloor\frac{k}{x}\rfloor\rfloor=\lfloor\frac{k}{x}\rfloor$

$\therefore \lfloor\frac{k}{g(x)}\rfloor=\lfloor\frac{k}{x}\rfloor$

综上得，对于 $i\in[x,\lfloor\frac{k}{\lfloor\frac{k}{x}\rfloor}\rfloor]$,$\lfloor\frac{k}{i}\rfloor$的值相等

莫比乌斯函数

$\mu(n) = \begin{cases} 0, & \exists i \in [1,m],c_i>1 \\ 1, & m \equiv 0 \pmod 2,\forall i \in [1,m],c_i=1 \\ -1, & m \equiv 1 \pmod 2,\forall i \in [1,m],c_i=1 \end{cases}$

线性筛法

$ Code:$

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

莫比乌斯反演

狄利克雷卷积

对于 $h(n)=\sum_{d|n} f(d)*g(\frac{n}{d})$

记作 $h=f\otimes g$ ,若 $f,g$ 为积性函数,则 $h$ 也为积性函数

对于给定数论函数 $ f,g$

$f(n)=\sum_{d|n} g(d) \iff g(n)=\sum_{d|n} \mu(d)*f(\frac{n}{d})$

性质：

$\sum_{d|n} \mu(d) = [n=1]$
$\sum_{d|n} \phi(d) =n$

杜教筛

应用范围：对于积性函数 $ f(x)$ ,求 $S(n)=\sum_{i=1}^n f(i)$

若 $h=f\otimes g$

则 $\sum_{i=1}^{n} h(i)$

$=\sum_{i=1}^n \sum_{d|i} f(d)·g(\frac{i}{d})$

$=\sum_{i=1}^n g(i)\sum_{d=1}^{\lfloor\frac{n}{i}\rfloor} f(d)$

$=\sum_{i=1}^n g(i) S(\lfloor\frac{n}{i}\rfloor)$

$=g(1)S(n)+\sum_{i=2}^n g(i)S(\lfloor\frac{n}{i}\rfloor)$

$\therefore S(n)=\frac{\sum_{i=1}^n h(i)-\sum_{i=2}^ng(i)S(\lfloor\frac{n}{i}\rfloor)}{g(1)}$

$Code:$

#pragma GCC optimize("O2")
#include<stdio.h>
#include<map>
using namespace std;
#define ll long long
#define re register
#define N 6000001

template<class T>
inline void read(T &x){
    x=0;char c=getchar();T flag=1;
    while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
    x*=flag;
}

map<ll,ll> mp1,mp2;
ll phi[N],mu[N];
int p[N],cnt=0;
bool mark[N];
inline ll dfs1(ll x){
    if(x<N) return phi[x];
    if(mp1[x]) return mp1[x];
    ll ans=1LL*(1+x)*x/2;
    for(re ll l=2,r;l<=x;l=r+1){
        r=(x/(x/l));
        ans-=(r-l+1)*dfs1(x/l);
    }
    return mp1[x]=ans;
}
inline ll dfs2(ll x){
    if(x<N) return mu[x];
    if(mp2[x]) return mp2[x];
    ll ans=1;
    for(re ll l=2,r;l<=x;l=r+1){
        r=(x/(x/l));
        ans-=(r-l+1)*dfs2(x/l);
    }
    return mp2[x]=ans;
}
int T;
ll n;
int main(){
    mark[1]=phi[1]=mu[1]=1;
    for(re int i=2;i<N;i++){
        if(!mark[i]){
            p[++cnt]=i;
            phi[i]=i-1;
            mu[i]=-1;
        }
        for(re int j=1;j<=cnt&&i*p[j]<N;j++){
            mark[i*p[j]]=1;
            if(!(i%p[j])){
                mu[i*p[j]]=0;
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }else{
                mu[i*p[j]]=-mu[i];
                phi[i*p[j]]=phi[i]*(p[j]-1);
            }
        }
    }
    for(re int i=1;i<N;i++)
        phi[i]+=phi[i-1],mu[i]+=mu[i-1];
    read(T);
    while(T--){
        read(n);
        printf("%lld %lld\n",dfs1(n),dfs2(n));
    }
}