Bell数的Touchard同余 - Touchard's Congruence  [draft]

贝尔数 $B_n$ 的含义是基数为 $n$ 的集合划分成非空集合的划分数。它满足Touchard同余,对于素数$p$有: $$ \begin{aligned} B_{n+p} & \equiv B_{n+1}+B_{n}\pmod{p} \newline B_{n+p^m} & \equiv B_{n+1}+mB_{n}\pmod{p} \newline \end{aligned} $$ ...

September 12, 2022 · 1 min · Kenshin2438

斯特林数取模小素数 - Congruence for Stirling Number

笔者在此并不想涉及过多的组合内容,其一,诸如此类的介绍文章在zhihu和csdn已经大量存在;其二,笔者并无自信将斯特林数的知识点吃透,也不觉得自己能够在这种理解程度下,提供什么特别的内容。 ...

September 1, 2022 · 5 min · Kenshin2438

多项式Hash函数冲突概率的探究

Hash 简介 Hash 的思想很简单,通过某种映射将一个序列或者字符串对应到一个值域较小的值,自然,我们只希望这种映射关系是单射的。 常用的 Hash 函数是一个模意义下的整系数多项式(同余式),例如,对于字符串$S$,定义Hash函数: $$ h(S)=\left(\sum_{i=1}^{|S|}\mathrm{base}^{|S| - i} \times S_i \right) \bmod M $$ 那么,何为 Hash 冲突呢?对于另一个等长的串$T$,满足$T \neq S, h(T)=h(T)$,即: $$ h(T)-h(S) = \left(\sum_{i=1}^{n}\mathrm{base}^{n - i} \times (T_i - S_i) \right) \equiv 0 \pmod{M} $$ 注意到,我们的 Hash 函数中的$\mathrm{base},M$均为自定义的值,显然影响冲突概率的正好是这两数。如果固定模数$M$,随机基数$\mathrm{base}$来讨论这个问题,则只要看$\mathrm{base}\in[1,M)$有多少为该同余式的解。 $M$ 为素数 $\textrm{Lagrange}$定理 $$ f(x)=\sum_{i=0}^{n}a_i\times x^i \equiv 0 \pmod{M} $$ 满足$n>0,a_n \not\equiv 0 \pmod{M},M\in \mathrm{Prime}$,则上同余式最多$n$个解。 证明: 当$n=1$时,一次同余式$a_1x+a_0\equiv 0\pmod{M}$,由于$M\nmid a_1$,显然恰好一个解。 当$n\geq M$结论显然成立。 当$2 \leq n \leq M - 1$时,我们进行反证。假设上式有多余$n$个解(不妨令为$x_0,x_1,\dots,x_k,(k \geq n+1)$,并且$\forall i\neq j, x_i \not\equiv x_j\pmod{M}$) 由于: $$ f(x)-f(x_0)\equiv\sum_{i=0}^{k}a_i(x^i-x_0^i)=(x-x_0)g(x)\pmod{M} $$ 容易知道,此时的$g(x)$为一个$n-1$次多项式,且$[x^{n-1}]g(x)=a_n\not\equiv 0\pmod{M}$。...

March 22, 2022 · 1 min · Kenshin2438

一类同余方程(DLP)的解法 - BSGS  [draft]

$\text{Baby Step/Giant Step Algorithm}$ 用于解决这样一类同余方程的方法 $$a^x \equiv b\pmod c$$ 结合原根的知识还能解决模数有原根的$N$次剩余问题 $$x^n \equiv b\pmod c$$ ...

September 5, 2021 · 6 min · Kenshin2438

二次剩余 - Cipolla/Tonelli-Shanks

对于二次剩余式 $$x^2\equiv n\pmod p$$ 其中$p$为奇素数,且$p \nmid n$,求$x$。 ...

August 30, 2021 · 4 min · Kenshin2438

欧拉定理(数论) 及其拓展 - Extended Euler Theorem

$\forall a<m,(a, m)=1$,均有$a^{\varphi(m)}\equiv1\pmod{m}$,于是就有欧拉定理: $$a^n\equiv a^{n \mod \varphi(m)} \pmod{m}$$ 对于$n$取值较大的情况(比如$10^{30000}\mod 13$),欧拉降幂的作用不可忽视,但局限的是必须满足$(a,m)=1$才能有上式恒成立。 由于上述形式流传甚广,读者大抵早已熟记于心,这里便不再赘述。本文的最终目的是介绍另一个适用范围更广的版本,即所谓拓展欧拉定理。 $$a^n\equiv a^{n \mod \varphi(m) + \varphi(m)} \pmod{m} \quad \textrm{if }n \geq \varphi(m)$$ ...

August 28, 2021 · 3 min · Kenshin2438

莫比乌斯反演问题记录 - Mobius Inversion

题外话:好像文章有点长,本地调的时候加载目录都掉帧了。虽然一度想删点题目,但思前想后还是一题没删,总感觉每一题都代表了一种典型,实在不好取舍,或许只写推导会好一点,但还是有点怕代码的实现未有较好交代。。。 好了,闲言少叙。 本篇是平时刷的反演题目的解题记录,个人认为这方面的知识点和写题目是有点脱节的,题目要么是纯套路,要么就是有些不太友好的小技巧。 题目来源:Luogu, LibreOJ, HDU等。 ...

August 27, 2021 · 16 min · Kenshin2438

筛法 - Sieve

logs Update 2021.10.03 增加PN筛 包含有: 线性筛,杜教筛,Min25筛,PN筛,州阁筛 本篇主要用于入门数论中的一些简单的筛法 虽然不是特别全面,但是后面会一步步完善的。 注意:不会对用到的数论函数解释,默认读者对数论有基本认知。 ...

July 28, 2021 · 12 min · Kenshin2438

孙子剩余定理 - CRT/exCRT

之前介绍Lucas定理时,内容涉及到了中国剩余定理,以及欧拉定理。 后者应该是广为人知的定理(之后也会写拓展欧拉定理的吧),然而前者的名气似乎远有不如。 本篇以证明为主,(不喜欢证明的可以关了)当然也会遵循传统给出板子。 ...

July 25, 2021 · 2 min · Kenshin2438

组合数取模 - Lucas/exLucas

info Update at 2022.1.19 修正FastMod代码来源。 证明和代码分开,可以根据自己的需要跳转。 ...

July 24, 2021 · 11 min · Kenshin2438