In mathematics you don't understand things, you just get used to them.

link。

构造函数 ans(x)ans(x)f(x)f(x) 分别表示 gcd\gcdxx 的链数和链 gcd\gcdxx 因子的链数,于是 f(x)=dxans(d)f(x)=\sum\limits_{d\mid x}ans(d),由莫比乌斯反演得 ans(x)=xdf(d)μ(dx)ans(x)=\sum\limits_{x|d}f(d)\mu(\frac{d}{x})

把每一个点权为 xx 的倍数的点拉出来,跑出各连通块大小可以平凡算出 f(x)f(x)

但是 ans(x)ans(x) 的计算一定需要莫反么?

代码给出的是容斥做法,via cqbzly。

maths

「atcoder - 214G」Three Permutations
上一篇 «
「codeforces - 1555F」Good Graph
» 下一篇