问题：有$n$个这样形式的方程组：$x\equiv c_i\mod m_i$。求通解和最小解。

一般的做法

考虑如何合并

定义

对于某一个$g\in [0,p)$，如果对于$\{0,1,\cdots p-1\}$中每一个与$p$互质的数$x$，都存在一个$k$使得$g^k \equiv x \mod p$，那么就称$g$是$p$的一个原根。也就是说，$g^0,g^1,\cdots g^{\varphi (n) - 1}$在模$n$的意义下两两不同。

公式 && 食用方法

设$Inv(i)$表示$i$在模$M$意义下的逆元，则有：
$Inv(i) \equiv (-\lfloor{M\over i}\rfloor ) \times Inv(M \mod i)\mod M$
由于$(M\mod i )< i$，所以可以利用这个公式线性预处理出逆元。

当模数比较小的时候，可以预处理出$[0,M)$的所有数的逆元，然后算法的复杂度就可以少一个$\log M$~

参考

OI-wiki

引入

勒让德记号

定义勒让德记号：

杜教筛是要记忆化的。但是$map$的常数非常大，亲测$Hash Table$也很难跑过现在luogu上的杜教筛模板。怎么办呢？如果我们能够预处理出所有会被用到的数，给他们分配好空间，那么不仅可以避开$map$的常数，还可以从小到大依次枚举这些数进行处理，从而避免递归。

观察$S(n)=h(n)-\sum_{i=2}^n S(\lfloor{n\over i}\rfloor)$，可知会被取到的数可以分为两类：

1.小于$\sqrt n$的所有自然数
2.一个大于$\sqrt n$的数$x$，并且存在一个小于$\sqrt n$的数，使$\lfloor {n\over i}\rfloor = x$成立。

原理

例题

loj6485 LJJ学二项式定理

概述

OI-wiki

另外一篇资料

参考资料

一篇tutorial
算法导论 31.9

食用方法

用于求积性函数的前$n$项的和，$n$通常在$10^{10}$左右。它要求这个函数必须是积性函数，并且对于质数，这个函数的取值可以表示成一个可以快速算前缀和并且完全积性的东西（比如低阶多项式），对于质数的k次方，这个函数大约可以在$O(1)$的时间内查询。

基本原理