不设背景了，直接说进制筛是啥。筛法在前面整除分块那里提过了，是广义的数学分类，特别对于进制函数大多数是杂乱无章的结果来说，筛的描述很恰当。还有，要说的话，进制筛不属于数论，进制筛就是进制相关的处理技术。

首先了解下什么是进制函数：进制函数就是指将数值$n$的某$k$进制表示上的各数位当作自变量的函数。鉴于，绝大多数进制函数处理的复杂度都是$O\left(\log N\right)$或$O\left(\log \log N\right)$。可以认为，复杂度不在这些以内的都是非进制函数。而一个整数函数可以分成进制函数和非进制函数的乘积或和。

进制筛就是指，对进制函数的可交换复合运算的分类处理，并得到一个描述这个运算的另一个进制函数，也就是说，进制筛是对许多进制函数的取值进行分类整理后又尝试获得一个新的进制函数的技术。（可交换复合运算，乘法、加法、异或、位交换运算（位与、位或）等等都是）

进制筛的原理：

1. 每一个$k$进制函数一定可以找到按$k$进制分块扩张的规律。（该命题称为进制规律）

2. 可交换的成组式的运算，依$\left\{k^p\right\}$会导致一个递归表达式，求出该式或者说这些值就是关键，是数学处理还是程序预先建表都是可以采取的方法，视情况大多数如果数学整理没法出现$O\left(\log \log N\right)$的结果那么本质上也几乎一定是一个$O\left(\log N\right)$的计算过程，那么除非要进一步再求它本身的进制规律，否则看自己的情况决定，一般来说，数学处理多多少少即使是$O\left(\log N\right)$也会降低很大的常数，但临场做题一定花费时间比直接怼着递归式写函数递归久得多。

3.

$$\sum_{i=0}^n f\left(i\right)=\sum_{i=0}^{n-k^p} f\left(k^p+i\right)+\sum_{i=0}^{k^p-1} f\left(i\right) $$$$\sum_{i=1}^n f\left(i\right)=\sum_{i=1}^{n-k^p} f\left(k^p+i\right)+\sum_{i=1}^{k^p} f\left(i\right) $$

该关系是正式将进制函数处理为$O\left(\log N\right)$的关键，其中进制规律保证了 $\sum_{i=0}^{k^p-1}f\left(i\right)$是$O\left(\log N\right)$ 甚至是$O\left(1\right)$的。同时还得注意，该式操作的时候一般是处理剩下部分的最高位，这个性质很重要的，可以归结为对各数位上不为零的位置进行的逐位分解。（该公式称为进制分解式，其中p为k进制最大位的幂）

所以总结进制筛的过程就是先分析进制函数的进制规律，然后整理可交换运算的结果（大概率是递归式），对递归式用程序或数学手段预处理。后使用进制分解式构建至多$O\left(\log N\right)$的算法。

举例 $\sum _{i=1}^n \text{lowbit}\left(i\right)$：

先观察$\text{lowbit}\left(i\right)$的进制规律，发现：

$$\text{lowbit} \left\{2^{n+1}\right\}=\left\{\text{lowbit} \left\{2^n\right\},\text{lowbit} \left\{2^n-1\right\},n+2\right\} $$

这个意思是初始状态是${1}$的数组，每次复制一倍接到后面，且最后一个变成原长度的对数$+2$

以上就是$\text{lowbit}$的进制规律。考虑$\sum _{i=1}^n \text{lowbit}\left(i\right)$，直接对进制规律全长进行求和，会得到：

$$\left\{\begin{matrix} L\left(n+1\right)=2L\left(n\right)+1 \\ L\left(0\right)=1 \end{matrix}\right. $$

求得$L\left(n\right)=2^{n+1}-1$

使用分解式对该式做处理会得到：

$$\sum_{k=0}^p a_k\left(2^{k+1}-1\right)$$

$a_k$是二进制展开的各位，即$n=\sum_{k=0}^p a_k 2^k$，取值范围当然是$\{0,1\}$。

由此最终变成了： $2n - \text{countbits}\left(n\right)$即：

$$\sum_{i=1}^n \text{lowbit}\left(i\right)=2n-\text{countbits}\left(n\right) $$

已知$\text{countbits}\left(n\right)$为$O\left(\log\log N\right)$，因此使用进制筛的策略将原先可能需要$O\left(N \log N\right)$的计算优化到$O\left(\log\log N\right)$。

其实本质来说，进制筛就是将可交换的计算（如前缀和），经过上述操作后也产生一个简便的进制函数，从而实现至多$O\left(\log N\right)$去计算前缀和的策略。不过要注意的是，一般和整除分块合并时，没有这种特效，因为整除分块的复杂度至少$O\left(\sqrt{N}\right)$，进制函数算得再快也没法掩盖整除分块算得慢。而一般多项式之类的初等函数的结果其实是$O\left(1\right)$，对于这种结构，一般采取$Abel$变换的策略逐步差分提纯进制函数，进制函数找进制规律，非进制函数纯数学手段求和。

所以，遇到进制函数极大可能是有简便的算法的，数据大小一般也会$10^{18}$拉满，而且一秒的样例还非常大（视情况最多可以处理接近$10^{7}$的秒量级，网上大部分不从进制筛的角度完全剖析，而只实现一定程度的分块，故而最大只能处理$10^{5}$水平，其方法可以参考，兴许分析程度没有进制筛这么全面和复杂，但容易分析出来，但我声明是进制筛的题，数据量至少$10^{6}$，绝对不会让任何简单的分块能通过的）。而涉及数论了之后，即使暴力也至少有$10^{9}$的数据大小。因此卡到$10^{6}$以上的都不是卡常这种简单的问题了，是复杂度出了问题。