2025 XYD Summer Camp 7.10 筛法

筛法

给定 $n,m$，求 $\forall i\in [1,n],j\in [1,m]$，$i,j$ 互质的对数。

$n,m\le 10^{10}$。

最终只需计算 ${\sum }_{d=1}^{\min (n,m)}\mu (d)\lfloor n/d\rfloor \lfloor m/d\rfloor$，瓶颈在于计算 $\mu$ 在若干个点上的前缀和，这些点一定属于 $n$ 或 $m$ 的整除点集合 $D_n,D_m$（就是使得 $\lfloor n/i\rfloor \ne \lfloor n/(i+1)\rfloor$ 的 $i$）。我们希望能在 $O(n)$ 以下的时间复杂度求出 $\forall i\in D_n\cup D_m,{\sum }_{j=1}^i\mu (j)$。

• 筛法：筛出质数，或者求一些积性函数的点值 / 前缀和。

杜教筛

这是一个关于 $G$ 的一个递推式，后面一个求和式可以使用整除分块，于是求解 $G(n)$ 我们需要求解 $n$ 的所有整除点上的 $G$，恰好符合问题所求；而递归下去又要求解所有整除点的整除点的……的整除点上的 $G$，根据整除性质可得这些点的 $G$ 也是我们需要求解的 $n$ 的某些整除点的 $G$。

• 整除性质：$\lfloor \frac{\lfloor \frac{n}{i}\rfloor }{j}\rfloor =\lfloor \frac{n}{ij}\rfloor$，我的整除的整除还是我的整除。

现在问题变成快速求 $f,h$ 的前缀和。注意到 $1\ast \phi =\mathrm{id}$，$1\ast \mu =ϵ$，且 $1,\mathrm{id},ϵ$ 前缀和很好求，于是就可以快速求 $\phi ,\mu$ 在 $n$ 整除点上的前缀和。

直接使用杜教筛的时间复杂度是 $O(n^{3/4})$ 的，考虑使用线性筛算出所有 $i\in [1,n^{2/3}]$ 的 $G(i)$ 的值，这样时间复杂度就平衡成 $O(n^{2/3})$，即算出所有 $n$ 的整除点处 $g$ 的前缀和的时间复杂度。

给定 $n,m$，求 $\forall i\in [1,n],j\in [1,m]$，$i,j$ 互质的对数。

$n,m\le 10^{10}$。

直接使用杜教筛算出 $n,m$ 所有整除点处的 $\mu$ 的前缀和即可。

给定 $n,k,l,r$，求从 $[l,r]$ 中选 $n$ 个整数使得选出的数的 $\gcd$ 恰好为 $k$ 的方案数。

$n,k\le 10^9$，$1\le l\le r\le 10^9$，有 $T\le 10$ 组数据。

设 $f(k)$ 表示这个问题的答案， 另设 $g(k)$ 表示选出的数是 $\gcd$ 的倍数的方案数，显然此时只要求选出的数是 $k$ 的倍数，于是有 $g(k)=(\lfloor r/k\rfloor -\lfloor (l-1)/k\rfloor {)}^n$。根据两个函数的定义有 $g(k)={\sum }_{k|i}f(i)$，莫比乌斯反演可得
$$\begin{array}{rl}f(k)& =\sum _{k|i}\mu (k/i)g(i)\\ & =\sum _{i\in {\mathbb{N}}^{\ast }}\mu (i)g(ik)\\ & =\sum _{i\in {\mathbb{N}}^{\ast }}\mu (i)\left(\lfloor \frac{\lfloor r/k\rfloor }{i}\rfloor -\lfloor \frac{\lfloor (l-1)/k\rfloor }{i}\rfloor \right)\end{array}$$
整除分块即可。注意到两个整除只要有一项非 $0$ 就有贡献，因此枚举时应枚举到 $r$ 而不是 $l-1$。

给定 $n,m,k$，求 $\forall x\in [1,n],y\in [1,m]$ 满足 $\frac{x}{y}$ 在 $k$ 进制下表示成小数形式后，小数部分可以表示成 $\overline{c_1{c}_2{c}_3\cdots c_p{c}_1{c}_2\cdots }$ 的无限循环形式的 $(x,y)$ 对数。分数值相同只算一次。

$1\le n,m\le 10^9$，$2\le k\le 2\times 10^3$。

假设 $k=10$，那么对于分数 $\frac{x}{y}$，因为 $x,y$ 都是正的所以其小数部分为 $\frac{x}{y}-\lfloor \frac{x}{y}\rfloor$；若这个分数是合法的，考虑把这个分数的小数点右移若干位 $l$，即 $\frac{x10^l}{y}$ 的小数部分 $\frac{x10^l}{y}-\lfloor \frac{x10^l}{y}\rfloor$ 应当与原来的小数部分一样。十进制下是乘 $10^l$，那么 $k$ 进制下就是乘 $k^l$。
$$\begin{array}{rl}\frac{x}{y}-\lfloor \frac{x}{y}\rfloor & =\frac{x{k}^l}{y}-\lfloor \frac{x{k}^l}{y}\rfloor \\ x-y\lfloor \frac{x}{y}\rfloor & =x{k}^l-y\lfloor \frac{x{k}^l}{y}\rfloor \end{array}$$
注意到这个式子相当于 $x,x{k}^l$ 对 $y$ 取模后相当，于是有
$$x\equiv x{k}^l(\mathrm{mod}y)$$
因为分数值相同的分数只记录一次贡献，因此我们只算最简分数的分数值，即 $\gcd (x,y)=1$，那么 $x$ 在 $\mathrm{mod}y$ 意义下就有逆元，两边同时乘 $x^{-1}$ 得到
$$k^l\equiv 1(\mathrm{mod}y)$$
我们发现这个式子与欧拉定理 $a^{\phi (p)}\equiv 1(\mathrm{mod}p)$ 很像。考虑欧拉定理要求 $\gcd (a,p)=1$，那么当 $\gcd (k,y)=1$ 时只要 $l$ 取 $\phi (y)$ 就是一个合法的循环节长度。于是我们现在要求的式子就是
$$\sum _{i=1}^n\sum _{j=1}^m[\gcd (i,j)=1][\gcd (j,k)=1]$$

最终可以化简成
$$\sum _{d=1}^{\min (n,m)}[\gcd (d,k)=1]\mu (d)\lfloor \frac{n}{d}\rfloor \sum _{j=1}^{\lfloor m/d\rfloor }[\gcd (j,k)=1]$$
考虑令 $g(n)={\sum }_{i=1}^n[\gcd (i,k)=1]$，当枚举到 $i>k$ 时有 $\gcd (i,k)=\gcd (i-k,k)$，也就是说 $i$ 的贡献与 $i-k$ 相同；进一步推广，枚举 $i$ 的过程中 $[\gcd (i,k)=1]$ 的值以 $k$ 为循环节循环变化。注意到 $g(k)=\phi (k)$，于是有
$$g(n)=\lfloor \frac{n}{k}\rfloor \phi (k)+g(n\mathrm{mod}k)$$
预处理 $\forall i\in [0,k-1],g(i)$ 的值就可以快速计算 $g(n)$。

现在还差 $[\gcd (d,k)=1]\mu (d)$ 这一项，我们设其为 $q(d)=[\gcd (d,k)=1]\mu (d)$。显然这个函数是积性函数，考虑用杜教筛，构造出满足 $f\ast q=c$ 的函数 $f,c$。考虑把卷积展开：
$$\begin{array}{rl}c(n)& =\sum _{d|n}f(d)[\gcd (n/d,k)=1]\mu (n/d)\\ & =\sum _{d|n}f(d)\mu (n/d)[\gcd (n/d,k)=1]\end{array}$$
考虑 $\gcd (a,b)=1,\gcd (a,c)=1⟺\gcd (a,bc)=1$，我们考虑令 $f(d)=[\gcd (d,k)=1]$，那么有
$$\begin{array}{rl}c(n)& =\sum _{d|n}[\gcd (d,k)=1][\gcd (n/d,k)=1]\mu (n/d)\\ & =\sum _{d|n}[\gcd (n,k)=1]\mu (n/d)\\ & =[\gcd (n,k)=1]\sum _{d|n}\mu (n/d)\\ & =[\gcd (n,k)=1][n=1]=[n=1]\end{array}$$
我们就可以得到 $c=ϵ$，又发现 $f$ 的前缀和就是 $g$，然后就可以快乐杜教筛力（喜

Powerful Number

对于一个正整数 $n$，称 $n$ 是 powerful number 当且仅当 $n$ 的所有质因子次数至少为 $2$。

• $n$ 以内 powerful number 的个数是严格 $\Theta (\sqrt{n})$ 的。

• 枚举 powerful number 的方法：线性筛筛出 $O(\sqrt{n})$ 以内的质数，然后 dfs 枚举这些质数的次数即可。

• 因为 $h=f\ast g^{-1}$，积性函数卷积性函数的逆还是积性函数，因此只需要计算 $h(p^k)$ 上的值，然后乘起来即可。有两种方法：
  • 直接推一个关于 $p,k$ 的式子表示出 $h(p^k)$；
  • 考虑 $f=h\ast g$，展开有 $f(p^k)={\sum }_{i=0}^{k}g(p^i)h(p^{k-i})$，把 $i=0$ 这一项提出并移项，可得 $h(p^k)=f(p^k)-{\sum }_{i=1}^{k}g(p^i)h(p^{k-i})$，可以递推求解，也可以预处理。

给定函数 $f(x)$，满足：

• $f(1)=1$；
• $f(p^c)=p\mathrm{xor}c$，其中 $p$ 是质数，$c$ 是正整数；
• $f(ab)=f(a)\times f(b)$，其中 $\gcd (a,b)=1$。

给定 $n$，求
$$\left(\sum _{i=1}^{n}f(i)\right)(\mathrm{mod}10^9+7)$$

从第二条可以推出对于质数 $p$，当 $p=2$ 时 $f(p)=p+1$；否则 $f(p)=p-1$。我们构造函数 $g$，满足当 $x$ 是偶数时 $g(x)=3\phi (x)$，否则 $g(x)=\phi (x)$。容易证明 $g$ 是积性函数，设 $G(n)={\sum }_{i=1}^{n}g(i)$，根据 PN 筛的公式有
$$\sum _{i=1}^{n}f(i)=\sum _{i=1}^n[i\text{ is powerful}]h(i)G(\lfloor n/i\rfloor )$$
其中 $h=f\ast g^{-1}$。假设已经知道 $G$ 在 $n$ 的整除点上的取值，那么现在只差 $h$ 在 powerful number 上的取值。在 dfs 枚举 powerful number 的过程中，假设枚举到质数 $p$ 的 $c$ 次方，现在枚举到的 powerful number 是 $d=d^{\prime }\times p^c$，并且我们已经求得 $h(d^{\prime })$。显然 $d^{\prime }$ 与 $p^c$ 互质，于是 $h(d)=h(d^{\prime })\times h(p^c)$，$h(p^c)$ 可以用递推的方法预处理并且存下来。

现在考虑算 $G(n)$。
$$\begin{array}{rl}G(n)& =\sum _{i=1}^{\lfloor n/2\rfloor }3\phi (2i)+\sum _{i=1}^{n-\lfloor n/2\rfloor }\phi (2i-1)\\ & =\sum _{i=1}^n\phi (i)+2\sum _{i=1}^{\lfloor n/2\rfloor }\phi (2i)\end{array}$$
第一个求和可以用杜教筛，令 $s(n)={\sum }_{i=1}^n\phi (2i)$，考虑分别计算 $i$ 是奇数和偶数的情况：
$$s(n)=\left(\sum _{i=1}^{\lfloor n/2\rfloor }\phi (2(2i-1))+\phi (2(2i))\right)+[n\mathrm{mod}2=1]\phi (2n)$$
注意到 $2i-1$ 总是与 $2$ 互质，于是前一项就等于 $\phi (2)\cdot \phi (2i-1)=\phi (2i-1)$；而 $2i$ 总是 $2$ 的倍数，于是后一项就等于 $2\phi (2i)$。于是可以发现 $s(n)=s(\lfloor n/2\rfloor )+{\sum }_{i=1}^n\phi (i)$，可以递归计算。