整除性校验的本质
从小学开始我们就知道, 一个数能被 \(3\) 整除当且仅当其各位数字之和能被 \(3\) 整除. 一个数能被 \(4\) 整除, 当且仅当其最后 \(2\) 位数能被 \(4\) 整除. 一个数能被 \(11\) 整除, 当且仅当其奇数位减去偶数位数字之和能被 \(11\) 整除(个位数记为第 \(1\) 位).
考虑如何求解以下方程 ：
显然可以转化为 ：
有裴蜀定理 :
对于不定方程 \(ax+by=c\)，其有解当且仅当 \(\gcd(a,b)|c\)。
可以发现上述方程有解当且仅当 \(\gcd(a,b)=1\)，故可以转化为 ：
\(\large\rm Proof:\)
将上式带入下式得 \(:\)
整理得 \(:\)
根据组合恒等式 \(\dbinom{i}{j}\dbinom{j}{k}=\dbinom{i}{k}\dbinom{i-k}{j-k}\) 得 \(:\)
交换枚举顺序得 \(:\)
杜教筛被用来求积性函数的前缀和。
设有积性函数 \(f(x)\)，其前缀和为 \(S(n) = \sum \limits_{i = 1}^{n} f(i)\)。
考虑构造 \(h(x)\) 和 \(g(x)\)，满足 \(h = f \times g\)。
推一下式子 ：
称使得 \(a^{t}\equiv 1\pmod p\) 成立的最小正整数 \(t_{min}\) 为 \(a\) 对模数 \(p\) 的阶，记为 \(\delta_{p}(a)\)。
有如下定理 ：\(g_{min}\lt p^{\frac{1}{4}}\)。