快速莫比乌斯变换（FMT）与莫比乌斯反演 例题：树上lcm

快速莫比乌斯变换

数学公式

• 记$S$为全集，$T$为其子集
  $$\begin{array}{rl}& zeta变换:F(S)=\sum _{T\subseteq S}f(T)\\ & \\ & 莫比乌斯反演:f(S)=\sum _{T\subseteq S}(-1{)}^{|S|-|T|}F(T)\end{array}$$
• $zeta$变换与$sosdp$中的子集求和、超集求和一致，只不过这里的集合范畴不仅限于二进制集合
• 莫比乌斯反演的作用就在于将超集和或者子集和反演为原来的函数

代码实现（二进制集合）

$zeta$变换(子集和)

伪代码：

for 每一位 bit i:for 每个 mask:如果 mask 有第 i 位:F[mask] += F[mask 去掉第 i 位]

代码：

void zeta(vector<ll> &f, int n) {for (int i = 0; i < n; i++) { // 枚举每一位for (int mask = 0; mask < (1 << n); mask++) {if (mask & (1 << i)) { // 如果第 i 位是 1f[mask] += f[mask ^ (1 << i)];}}}
}

$Mobius$反演

伪代码：

for 每一位 bit i:for 每个 mask:如果 mask 有第 i 位:F[mask] -= F[mask 去掉第 i 位]

代码：

void mobius(vector<ll> &f, int n) {for (int i = 0; i < n; i++) {for (int mask = 0; mask < (1 << n); mask++) {if (mask & (1 << i)) {f[mask] -= f[mask ^ (1 << i)];}}}
}

---

数论中的莫比乌斯反演

若有：
$$F(n)=\sum _{d|n}f(d)$$
其中$d|n$表示$d$为$n$的因数
则有：
$$f(n)=\sum _{d|n}\mu (d)\cdot F\left(\frac{n}{d}\right)$$
其中$\mu (d)$为数论莫比乌斯函数，对应着莫比乌斯反演中的$(-1{)}^{|S|-|T|}$；$n$对应着全集$S$；$\frac{n}{d}$对应着子集$T$

莫比乌斯函数的定义：
$$\mu (n)=\{\begin{array}{l}\begin{array}{rlr}& 1,& n=1\\ & & \\ & (-1{)}^k& n是k个不同质数的乘积\\ & & \\ & 0& n有平方因子\end{array}\end{array}$$

基于欧拉筛的$\mu$函数代码：

int mu[MX], vis[MX], p[MX], cnt;
void init() {mu[1] = 1;rep(i, 2, MX - 1) {if (!vis[i])p[++cnt] = i, mu[i] = -1;for (int j = 1; i * p[j] < MX; j++) {vis[i * p[j]] = 1;if (i % p[j] == 0)break;mu[i * p[j]] = -mu[i];}}
}

例题：树上lcm

思路

设$f(x)$为路径$lcm$为$x$的简单路径数
由于涉及因数与求和，联想到莫比乌斯反演
$$设f(x)=\sum _{d|x}\mu (d)g\left(\frac{x}{d}\right)$$
由莫比乌斯反演：
$$g(n)=\sum _{d|n}f(d)$$
因此得到$g(n)$的定义：路径$lcm$为$n$的因数的简单路径数

因此可以先将整棵树上不是$x$的因数的节点删去，此时每个连通块内的任意两点构成的简单路径的$lcm$都是$x$的因数！

dfs染色统计每个连通块的大小，计算有多少条简单路径即可

代码实现

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<unordered_map>
#include<set>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(ll i = (a); i <= (b); i ++)
#define per(i, a, b) for(ll i = (a); i >= (b); i --)
//#define see(stl) for(auto&ele:stl)cout<<ele<<" "; cout<<'\n';
#define int ll
const int N = 1e5 + 5;
const int MX = 1e7 + 5;
int n, x;
struct node {vector<int>e;int val, tag, siz;
}a[N];ll gcd(ll a, ll b) {if (b == 0)return a;return gcd(b, a % b);
}
ll lcm(ll a, ll b) {return a * b / gcd(a, b);
}void dfs(int u, int fa, int fac) {if (lcm(a[u].val, fac) > fac)a[u].tag = -1;else a[u].tag = 0;for (auto& son : a[u].e) {if (son == fa)continue;dfs(son, u, fac);}
}void dfs2(int u, int fa) {a[u].tag = 1; a[u].siz = 1;for (auto& son : a[u].e) {if (son == fa || a[son].tag != 0)continue;dfs2(son, u);a[u].siz += a[son].siz;}
}int mu[MX], vis[MX], p[MX], cnt;
void init() {mu[1] = 1;rep(i, 2, MX - 1) {if (!vis[i])p[++cnt] = i, mu[i] = -1;for (int j = 1; i * p[j] < MX; j++) {vis[i * p[j]] = 1;if (i % p[j] == 0)break;mu[i * p[j]] = -mu[i];}}
}void eachT() {set<int>fac;rep(i, 1, n)a[i].e.clear(), a[i].tag = 0,a[i].siz=1;cin >> n >> x;rep(i, 1, n - 1) {int u, v; cin >> u >> v;a[u].e.push_back(v), a[v].e.push_back(u);}rep(i, 1, n)cin >> a[i].val;for (int i = 1; i * i <= x; i++) {if (x % i == 0)fac.insert(i), fac.insert(x / i);}ll ans = 0;for (auto& f : fac) {ll now = 0;dfs(1, 0, f);rep(i, 1, n) {if (a[i].tag == 0) {dfs2(i, 0);int s = a[i].siz;now += s * (s - 1) / 2 + s;}}ans += now * mu[x / f];}cout << ans << '\n';
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);init();ll t = 1;cin >> t;while (t--) { eachT(); }
}