莫比乌斯反演

2018-08-16

整数分块

比如：
$\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor$
$O(n)$ 的做法之外，还有一种 $O(\sqrt{n})$ 的做法。

对于每个 $\lfloor\frac{n}{i}\rfloor$ 我们可以通过打表发现有许多的值是不断重复的，再继续寻找规律（不会找啊Orz）发现每一块的数字都是n/(n/i)，那么就可以利用分块的道理：

for(int l=1,r;l<=n;l=r+1)
{
    r=n/(n/l); //右边的数应当取min，这里只有一个n就没关系
    ans+=(r-l+1)*(n/l);
    //这里根据情况改啊！r-（l-1）是因为这里的积性函数可以看作是μ(i)=1，n/l是后面的那个n/i
}

有时候可能推出来的式子没有这么裸，它可能乘了一个积性函数 $\mu,\varphi$ ，这时候就要对这些函数统计一个前缀和，因为当我们跳过一个分块的时候，就相当于跳过了这个块的函数值。

P.S. 当 $O(n)$ 也T，杜教筛？？？？？？？？？？？？

莫比乌斯函数μ(d)

定义：

d = 1时，μ(d) = 1；
d = $\Pi_{i=1}^{k}p_i$ ，pi为互不相同的素数时， $μ(d) =(-1)^k$ （也就是说，当用于乘积的某一个质因子的次数不大于1时，μ值由用于乘积的质因子个数决定）；
其他情况，都为0 。

性质：

$\sum_{d|n}μ(d) = (n=1)$
$\sum_{d|n}\frac{μ(d)}{d} = \frac{φ(n)}{n}$ ,其中φ为小于n与n互质的数字的个数

/** 对于μ函数的线筛 */
int mu[N],prim[N];
bool vis[N]={0};
int cnt=0;
void get_mu(int n)
{
	mu[1]=1;
	for(int i=2;i<=n;i++)
	{
    	if(!vis[i]){prim[++cnt]=i;mu[i]=-1;}
   	 	for(int j=1;j<=cnt&&prim[j]*i<=n;j++)
        {
        	vis[prim[j]*i]=1;
        	if(i%prim[j]==0)break;
        	else mu[i*prim[j]]=-mu[i];
    	}
	}
}

有时候要同时求φ(x)和μ(x)，整合版：

/*mu为μ，phi为φ */
const int maxn = 1000000 + 5;
int phi[maxn],mu[maxn],prim[maxn];
bool vis[maxn]={0};
int cnt=0;

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



/** 做题时看到一版少开一个数组的*/
const int maxn = 1e6+100;
typedef long long ll;
int fac[maxn],miu[maxn],phi[maxn];
void init()
{
    for(int i=1;i<maxn;++i) fac[i]=i;
    phi[1]=miu[1]=1;
    for(int i=2;i<maxn;++i)
    {
        if(fac[i]==i)
            for(int j=i<<1;j<maxn;j+=i)
                fac[j]=i;
        if(i/fac[i]%fac[i]) phi[i]=(fac[i]-1)*phi[i/fac[i]],miu[i]=-miu[i/fac[i]];
        else phi[i]=fac[i]*phi[i/fac[i]],miu[i]=0;
    }
}

莫比乌斯反演

定理：F(n)和f(n)是定义在非负整数集合上的两个函数，并且满足条件：
$F(n)=\sum_{d|n}f(d)$
那么参考容斥的话，就能推出：
$f(n)=\sum_{d|n}μ(d)F(\frac{n}{d})$
一个更好用的形式，当满足：
$F(n)=\sum_{n|d}f(d)$
有：
$f(n)=\sum_{n|d}μ(\frac{d}{n})F(d)$