莫比乌斯反演

Overview – \mu(n)

莫比乌斯函数:先根据算术基本定理,令 n = {p_1}^{e_1} * {p_2}^{e_2} * {p_3}^{e_3} * {…} * {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]

发表评论

电子邮件地址不会被公开。 必填项已用*标注