洲阁筛学习笔记

main.tex

\documentclass[12pt]{ctexart}
    \usepackage{amsmath,mathtools,physics}
    \DeclareMathOperator{\maxp}{maxp}
    \newtheorem{lemma}{引理}
    \title{洲阁筛学习笔记}
    \date{2018/6/25}
    \begin{document}
    \maketitle
    \section{前言}
    ``洲阁筛''是求一类特殊的积性函数的前缀和的算法。
    名字里的洲字可能是指任之洲，因为他在2016年的集训队论文中介绍了这个算法，阁字的由来我尚不清楚，筛字是由于这个算法跟质数筛法关系密切。下文中不会提到这个名称。
    笔记的主题是此算法的实现细节，不分析复杂度。
    \section{推导}
    对于正整数 $n$，令 $m = \lfloor \sqrt{n}\rfloor $，用 $[1..n]$表示区间 $[1,n]$ 中的整数；若 $n\ge 2$，用 $\hat p(n)$ 表示 $n$ 的最大质因子，用 $\check p(n)$ 表示 $n$ 的最小质因子；用 $D(n)$表示$n$的质因子构成的集合，特别地，$D(1)=\emptyset$。符号 $p$ 总是代表质数。
    \begin{lemma}
        $\forall i \in [1..n]$，$i$ 至多有一个大于$m$ 的质因子，若 $\exists p > m$ 使得 $p\mid i$ 则 $i/p \le m$ 。
    \end{lemma}  
    \begin{lemma}
        对于任意正整数 $a,b,c$， $\lfloor a/(bc)\rfloor = \lfloor \lfloor a/b \rfloor / c \rfloor$。
    \end{lemma}  
    %将 $[1..m]$ 分成两部分 $A\coloneqq \{1\}\cup\{i\in[2..n]\colon \bar p(i)\le m]\}$，$B\coloneqq \{i\in[2..n]\colon \bar p(i) > m]\}$。
    设 $f$ 是积性函数，则
    \begin{equation}
        \sum_{i=1}^{n} f(i) =  \sum_{\hat p(i)\le m} f(i) + \sum_{i=1}^m f(i) \sum_{m < p \le \lfloor\frac{n}{i}\rfloor} f(p)\label{E:1}
    \end{equation}
    % 注意到 \eqref{E:1} 式右边的两项都是\emph{筛选}出最大素因子\footnote{第二项是筛素数，而素数可以看成满足 $\hat p(n) = n$ 的数。}满足某些条件的数，再对这些数的函数值求和。
    
    先求 $\sum_{\hat p(i)\le m} f(i)$。
    设 $[1..m]$ 中的素数\emph{从大到小}依次为 $p_1, p_2, \dots, p_c$，令$P_i = \{p_1, p_2， \dots, p_i\},1\le i\le c$，$P_0 = \emptyset$。令 $S_{i,j} = \{k\in [1..j]\colon D(k)\subseteq P_i\}, 1\le i\le c$，则
    \[\sum_{\hat p(i)\le m} f(i) = \sum_{i \in S_{c,n}} f(i)\]
    关于 $S_{i,j}$，我们有 $S_{0,j} = \{1\}$；当 $j<p_i$ 时，有$S_{i,j} = \qty{1}$；当 $ p_i \le j < p_i^2$ 时\footnote{$\forall k\in S_{i,j}$且$k\ge 2$，有$\check{p}(k) \ge p_i$，所以当 $j<p_i^2$时，$k$是质数。}，有 $S_{i,j} = \qty{1} \cup\qty(P_i \cap [p_i..j])$。$S_{i,j}$ 满足如下递推
    \begin{equation}
        S_{i,j} = S_{i-1,j} \cup \bigcup_{k\ge 1} \qty{lp_i^k\colon l\in S_{i-1,\lfloor j/p_i^k\rfloor}}\label{E:2}
    \end{equation}
    固定 $j$，当 $p_i^2 \le j$ 时，用 \eqref{E:2} 式计算 $S_{i,j}$。从 \eqref{E:2} 式可以看出，在递推计算 $S_{c,n}$ 的过程中， 下标 $j$ 只能取到 $O(\sqrt{n})$ 个不同的值。
    
    再求 $\sum_{i=1}^m f(i) \sum_{m < p \le \lfloor\frac{n}{i}\rfloor} f(p) $。将 $[1..m]$ 中的质数\emph{从小到大}依次记作$p_1, p_2, \dots, p_c$，令$P_i = \{p_1, p_2， \dots, p_i\},1\le i\le c$，$P_0 = \emptyset$。令 $T_{i,j} = \{k\in[1..j]\colon D(k)\cap P_i = \emptyset\}$，则
    \[
        \sum_{i=1}^m f(i) \sum_{m < p \le \lfloor\frac{n}{i}\rfloor} f(p) = \sum_{i=1}^m f(i) \sum_{p\in T_{c,\lfloor n/i\rfloor}} f(p)
    \]
    关于 $T_{i,j}$，我们有$T_{0,j} = [1..j]$，当 $j < p_{i+1}$ 时，$T_{i,j} = \qty{1}$。
    %当 $j \le p_i$ 时\footnote{这个条件可放宽为 $j < p_{i+1}$，但是在编程实现时采用$j \le p_i$更为方便。}，$T_{i,j} = \qty{1}$，当 $p_i < j \le p_i^2$ 时\footnote{这个条件可以精确为 $p_{i+1}\le j < p_{i+1}^2$。}，$T_{i,j} = \qty{1}\cup \qty{p\colon p\in[p_{i+1}..j]}$\footnote{这个式子没错，但不能用于求解 $T_{i,j}$，原因是我们不知道 $[m+1..n]$ 中的质数有哪些。}。
    $T_{i,j}$ 满足如下递推
    \begin{equation} 
        T_{i,j} = T_{i-1,j} \backslash \qty{kp_i\colon k\in T_{i-1,\lfloor j/p_i \rfloor}} \label{E:3}
    \end{equation}
    当 $j \ge p_{i+1}$ 时，需要用 \eqref{E:3} 式来计算 $T_{i,j}$；但是由于我们不知道大于 $m$ 的质数有哪些，所以我们避免用到 $p_{i+1}$，当 $j > p_i$ 时，就采用 \eqref{E:3} 式来计算 $T_{i,j}$。 
    当 $\lfloor j/p_i \rfloor < p_i $ 即 $p_i < j < p_i^2$ 时，$T_{i-1,\lfloor j/p_i \rfloor}=\qty{1}$，\eqref{E:3} 式变为
    \begin{equation}
        T_{i,j} = T_{i-1,j} \backslash \qty{p_i} \label{E:4}
    \end{equation}
    \eqref{E:4} 式是一个关于 $i$ 的递归式，若又有 $j < p_{i-1}^2$，则 $T_{i-1,j} = T_{i-2,j}\backslash\qty{p_{i-1}} $，从而 $T_{i,j} = T_{i-2,j}\backslash \qty{p_i, p_{i-1}}$，类推下去，当 $p_i < j < p_k^2$ 时，有 
    \[T_{i,j} = T_{k-1,j} \backslash \qty{p_k, p_{k+1}, \dots, p_i}\]
    至此，我们发现，只有当 $p_i^2 \le j$ 时，才需要用 \eqref{E:3} 式来计算 $T_{i,j}$。
    
    \section{实现}
    \begin{lemma}
    对于任意正整数 $a,b$，设 $a\ge b$，令 $c = \lfloor a/b \rfloor$，则 $\lfloor a/c \rfloor \ge b$，当且仅当 $b\mid a$ 时取等号，且 $c$ 是使得 $\lfloor a/i \rfloor \ge b$ 的正整数 $i$ 中的最大者。
    \end{lemma}
    \begin{lemma}
        设 $j_1 = \lfloor n/t_1 \rfloor，j_1>m$，$j_2 = \lflo
    \end{lemma}
    % 固定 $j$，当 $p_i^2 < j$ 时，用 \eqref{E:3} 式计算 $T_{i,j}$。
    %$1\le\lfloor j/p_i\rfloor < p_i < p_{i-1}$，有 $S_{i-1,\lfloor j/p_i\rfloor} = \qty{1}$，从而 $S_{i,j} = S_{i-1,j} \cup \qty{p_i}$  
      
    % \[
    %     S_{i,j} = 
    % \begin{cases}
    %      \{1\}, \quad p_i > j \\
    %      \{2\}
    % \end{cases}
    % \]
    \end{document}