莫比乌斯反演

Jul 28, 2018 由 小羊

Overview - $\mu(n)$

莫比乌斯函数：先根据算术基本定理，令 $n = {p_1}^{e_1} \times {p_2}^{e_2} \times {p_3}^{e_3} \times \cdots \times {p_k}^{e_k}$，则有

$\mu(n) = \begin{cases} \begin{array}{lcl} 0 & & when\,\exists\,{e_i}>1 \\\\ (-1)^k & & else \\ \end{array} \end{cases}$

例如，$\mu(1)=1$，$\mu(2)=-1$，$\mu(3)=-1$，$\mu(2 * 2)=0$，$\mu(2 * 3)=1$，$\mu(2 * 3 * 5)=-1$，$\mu(2 * 3 * 5 * 7)=1$……

一个验证较为稳定的莫比乌斯函数+欧拉函数+素数线性筛。

const size_t MAXN = 1e6+5;
char miu[MAXN], isnp[MAXN];
int phi[MAXN], pri[MAXN], p = 0, sum[MAXN];

void init_prime()
{
    miu[1] = 1; phi[1] = 1;

    for (int i = 2; i < MAXN; i++)
    {
        if (!isnp[i])
        {
            phi[i] = i-1;
            miu[i] = -1;
            pri[p++] = i;
        }

        for (int j = 0; j < p; j++)
        {
            int k = pri[j] * i;
            if (k >= MAXN) break;
            isnp[k] = 1;
            if (i % pri[j] == 0)
            {
                miu[k] = 0;
                phi[k] = phi[i]*pri[j];
                break;
            }
            else
            {
                phi[k] = phi[i]*(pri[j]-1);
                miu[k] = -miu[i];
            }
        }
    }

    sum[0] = 0; // 分块求和预处理 miu - 前缀和
    for (int i = 1; i < MAXN; i++)
        sum[i] = sum[i-1] + miu[i];

} // phi前缀和有n^2/3杜教筛

Overview - 反演

F(n)=\sum_{d|n}f(d) \Rightarrow f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})

F(n)=\sum_{n|d}f(d) \Rightarrow f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)

这个反演和偏序关系的覆盖、整除关系的覆盖有关。组合数学和数论的结晶。反正我还是有那么一点点懵逼。

一个验证较为稳定的模板：

$f(x)$为 $x \in [1,b], ~ y \in [1,d], ~ gcd(x,y)==n$ 的对数，使用了分块求和，加速计算用的。很多题基本上用这个模板都可以解决，少数题略改也可以通过。

lld f(int b, int d, int n)
{
    if (!b || !d || !n) return 0;
    lld ret = 0;
    int last = -1;
    b /= n, d /= n;
    if (b > d) swap(b, d);
    for (int i = 1; i <= b; i = last + 1)
    {
        last = min(b / (b/i), d / (d/i));
        ret += 1LL * (sum[last] - sum[i-1]) * (b/i) * (d/i);
    }
    return ret;
}

A - Visible Lattice Points

求$a,b,c\in[0,n]$，使$gcd(a,b,c)=1$成立的个数。

双区间是$\left \lfloor n/i \right \rfloor * \left \lfloor n/i \right \rfloor$，三区间就是$\left \lfloor n/i \right \rfloor * \left \lfloor n/i \right \rfloor * \left \lfloor n/i \right \rfloor$呗。

不过，这个是 $[1,n]$ 的情况，要转为0起始的话，考虑$(0,b,c)\ (a,0,c)\ (a,b,0)\ (0,0,0)$，所以最后的反演公式是

$f(n)=\sum_{d|n} \mu(d) \left \lfloor \frac{n}{i} \right \rfloor\left \lfloor \frac{n}{i} \right \rfloor(\left \lfloor \frac{n}{i} \right \rfloor+3)$

B - GCD

考虑一下重叠区间内的元素个数，直接除以2好啦。

$f(b,d,k)-\lfloor\frac{f(t,t,k)}{2}\rfloor\ , t=min(b,d)$

C - Mophues

按n的素因子个数分类 $\mu(n)$，前缀和处理。

D - GCD of Sequence

好像是容斥吧。有待爆肝。

E - Gcd

先说莫比乌斯反演的做法。直接枚举所有小于他们的素数然后求和即可。

有一种欧拉函数前缀和的做法。考虑 $gcd(x,y)=p \Leftrightarrow gcd(\frac{x}{p},\frac{y}{p})=1$，则使用欧拉函数的定义吧。

递推求欧拉函数表应该也挺快的，不过注意$(1,x) (x,1) (1,1)$不在此中。

F - 能量采集

考虑 $cnt[gcd(a,b)=i]$，意味着 $(a,b), (0,0)$ 点之间有 $i-1$ 棵植物，花费 $2i-1$。则

$\sum_{i=1}^{\infty}(2 i-1) * f(n,m,i)$

注意 $i$ 到某个节点之后就为0了，可以结束计算。

G - Problem b

由于区间不一定是1开始的，考虑这样的一个容斥：

$[a,b] \times [c,d]=[1,b] \times [1,d]-[1,a-1] \times [1,d]-[1,b] \times [1,c-1]+[1,a-1] \times [1,c-1]$