CF803F Coprime Subsequences

CF803F Coprime Subsequences

题目简述

求一个序列 \(a\) 的互质子序列数量. 互质是指所有元素的 \(\gcd\) 为 \(1\).

\(n,V\leq 10^5\).

推导过程

令 \(B_x\) 表示 \(a\) 中 \(x\) 的倍数的数量.

令 \(f(x)\) 表示 \(a\) 中 \(\gcd=x\) 的子序列数量，\(g(x)\) 表示 \(a\) 中 \(x\mid\gcd\) 的子序列数量. 则

\[g(x)=2^{B_x}-1 \]

且

\[g(x)=\sum_{x|d}f(d) \]

那么，根据莫比乌斯反演，可得

\[\begin{align*} f(x)&=\sum_{x|d}\mu\!\left(\frac{x}{d}\right)\cdot g(d) \\ &=\sum_{d=ix}\mu(i)\cdot g(ix) \\ &=\sum_{i=1}^{\lfloor V/x\rfloor}\mu(i)\cdot g(ix) \end{align*} \]

那么，答案即 \(f(1)=\sum_{i=1}^V\mu(i)\cdot g(i)\).