2018年7月 – 小羊儿的心情天空

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]$

Overview – \mu(n)