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