Skip to content

Latest commit

 

History

History
18 lines (18 loc) · 226 KB

math.md

File metadata and controls

18 lines (18 loc) · 226 KB
Raw
<title>数论杂谈（by $KesdiaelKen$）</title>

数论杂谈（by <script type="math/tex" id="MathJax-Element-1">KesdiaelKen</script>）

目录：

逆元求法

整除分块

卡特兰数

逆元

逆元定义：已知正整数<script type="math/tex" id="MathJax-Element-2">a,b</script>，<script type="math/tex" id="MathJax-Element-3">(a,b)=1,a，求使得<script type="math/tex" id="MathJax-Element-4">ax\space mod \space b=1</script>的<script type="math/tex" id="MathJax-Element-5">x(1<=x<=b)</script>

问题

求1到n模p(p为质数且p>n)意义下的逆元

求法1 扩展欧几里得求

直接对于每一个都求一次

<script type="math/tex; mode=display" id="MathJax-Element-6">O(n \log{n})</script>

求法2 费马小定理

<script type="math/tex" id="MathJax-Element-7">\because a^{p-1}\equiv 1(mod\space p)</script>

<script type="math/tex" id="MathJax-Element-8">\therefore </script>设<script type="math/tex" id="MathJax-Element-9">ax\equiv 1(mod\space p)\space \therefore ax\equiv a^{p-1}(mod\space p)</script>

<script type="math/tex" id="MathJax-Element-10">\therefore x\equiv a^{p-2}(mod\space p)</script>

单个求：

<script type="math/tex; mode=display" id="MathJax-Element-11">O(n \log{n})</script>

优化：

有a的逆元为<script type="math/tex" id="MathJax-Element-12">a^{p-2}</script>，b的逆元为<script type="math/tex" id="MathJax-Element-13">b^{p-2}</script>，<script type="math/tex" id="MathJax-Element-14">ab</script>的逆元为<script type="math/tex" id="MathJax-Element-15">(ab)^{p-2}</script>

<script type="math/tex" id="MathJax-Element-16">\therefore x_a x_b=x_{ab}</script>

线性筛求解

<script type="math/tex; mode=display" id="MathJax-Element-17">O(n)</script>

求法3 递推公式

设<script type="math/tex" id="MathJax-Element-18">k^{-1}</script>表示k的逆元

设<script type="math/tex" id="MathJax-Element-19">p\div i=k...r \space\therefore p=ki+r</script>

<script type="math/tex" id="MathJax-Element-20">\therefore ki+r\equiv 0(mod\space p)\space</script>
<script type="math/tex" id="MathJax-Element-21">\therefore (ki+r)i^{-1}r^{-1}\equiv 0(mod\space p)</script>

<script type="math/tex" id="MathJax-Element-22">\therefore kr^{-1}+i^{-1}\equiv 0(mod\space p)\space \therefore i^{-1}\equiv (p-k)r^{-1}(mod\space p)</script>

<script type="math/tex" id="MathJax-Element-23">\therefore i^{-1}\equiv (p-p/i)(p\space mod\space i)^{-1}(mod\space p)</script>

<script type="math/tex; mode=display" id="MathJax-Element-24">O(n)</script>

求法4 阶乘求法

首先<script type="math/tex" id="MathJax-Element-25">O(\log n)</script>求<script type="math/tex" id="MathJax-Element-26">n!</script>逆元

有<script type="math/tex" id="MathJax-Element-27">((k-1)!)^{-1}= (k!)^{-1}*k\space mod\space p</script>

之后<script type="math/tex" id="MathJax-Element-28">O(n)</script>倒着递推求出<script type="math/tex" id="MathJax-Element-29">1!</script>到<script type="math/tex" id="MathJax-Element-30">n!</script>的逆元

又有<script type="math/tex" id="MathJax-Element-31">k^{-1}=(k!)^{-1}*(k-1)!</script>

再次递推求即可

<script type="math/tex; mode=display" id="MathJax-Element-32">O(n+\log n)</script>

整除分块

问题：求<script type="math/tex" id="MathJax-Element-33">\sum^n_{i=1}\lfloor\frac{n}{i}\rfloor</script>，
（当然不是只能在这个式子上应用，但它的确是最经常应用到整除分块的式子，没有之一）并将时间复杂度从<script type="math/tex" id="MathJax-Element-34">O(n)</script>降到<script type="math/tex" id="MathJax-Element-35">O(\sqrt n)</script>。

整除分块能实现基于这样一个事实：<script type="math/tex" id="MathJax-Element-36">\lfloor\frac{n}{i}\rfloor</script>的取值总共不会超过<script type="math/tex" id="MathJax-Element-37">2\sqrt n</script>种。为什么呢，我们来证明一下：

当<script type="math/tex" id="MathJax-Element-38">i<=\sqrt n</script>时：

我们需要证明：<script type="math/tex" id="MathJax-Element-39">\lfloor\frac{n}{i}\rfloor\not=\lfloor\frac{n}{i+1}\rfloor</script>

我们设<script type="math/tex" id="MathJax-Element-40">n\div i=k...s</script>，那么就有<script type="math/tex" id="MathJax-Element-41">n=i*k+s</script>。根据除法的性质，<script type="math/tex" id="MathJax-Element-42">s，而又因为<script type="math/tex" id="MathJax-Element-43">i<=\sqrt n</script>，所以<script type="math/tex" id="MathJax-Element-44">k>=\sqrt n>=i</script>，所以<script type="math/tex" id="MathJax-Element-45">s。

如果<script type="math/tex" id="MathJax-Element-46">\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{i+1}\rfloor</script>，那么<script type="math/tex" id="MathJax-Element-47">n</script>就可以表示为<script type="math/tex" id="MathJax-Element-48">(i+1)*k+p</script>（<script type="math/tex" id="MathJax-Element-49">p>=0</script>），即<script type="math/tex" id="MathJax-Element-50">n=i*k+s+(k+p-s)=n+(k+p-s)</script>。而我们又知道<script type="math/tex" id="MathJax-Element-51">k-s>0,p>=0</script>。所以<script type="math/tex" id="MathJax-Element-52">k+p-s>0</script>，即等式两边矛盾。所以由反证法我们就得到了<script type="math/tex" id="MathJax-Element-53">\lfloor\frac{n}{i}\rfloor\not=\lfloor\frac{n}{i+1}\rfloor</script>。因此，在此情况下<script type="math/tex" id="MathJax-Element-54">\lfloor\frac{n}{i}\rfloor</script>的取值个数就等于<script type="math/tex" id="MathJax-Element-55">i</script>的取值数，即<script type="math/tex" id="MathJax-Element-56">\sqrt n</script>种。

当<script type="math/tex" id="MathJax-Element-57">i>\sqrt n</script>时：

这个不用怎么说了吧……<script type="math/tex" id="MathJax-Element-58">\lfloor\frac{n}{i}\rfloor_{max}</script>都已经是小于<script type="math/tex" id="MathJax-Element-59">\sqrt n</script>的了，总取值数当然不超过<script type="math/tex" id="MathJax-Element-60">\sqrt n</script>啊。

所以，两类加起来就是<script type="math/tex" id="MathJax-Element-61">2\sqrt n</script>种了。

<script type="math/tex; mode=display" id="MathJax-Element-62">\mathcal{Q.E.D}</script>

既然证玩了这个结论，我们就可以考虑这样一个思路：因为<script type="math/tex" id="MathJax-Element-63">\lfloor\frac{n}{i}\rfloor</script>的取值数为<script type="math/tex" id="MathJax-Element-64">\sqrt n</script>（那个<script type="math/tex" id="MathJax-Element-65">2</script>是常数，可以忽略），那么只要求出它取每一种值时<script type="math/tex" id="MathJax-Element-66">i</script>的最大值和最小值是多少，最终求和的时候用前缀和预处理算一下每一段的值是多少，加起来就可以了。

那么接下来，我们又需要证明一个结论了：

如果已知正整数<script type="math/tex" id="MathJax-Element-67">p,n</script>（<script type="math/tex" id="MathJax-Element-68">n>=p</script>），则使<script type="math/tex" id="MathJax-Element-69">\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{p}\rfloor</script>的最大整数<script type="math/tex" id="MathJax-Element-70">i</script>的值就是<script type="math/tex" id="MathJax-Element-71">i_{max}=\lfloor\frac{n}{\frac{n}{p}}\rfloor</script>。

证明：

我们同样分类讨论一下。

当<script type="math/tex" id="MathJax-Element-72">p<=\sqrt n</script>时：

我们设<script type="math/tex" id="MathJax-Element-73">n\div p=k...s</script>，那么就有<script type="math/tex" id="MathJax-Element-74">n=p*k+s</script>。根据除法的性质，<script type="math/tex" id="MathJax-Element-75">s，而又因为<script type="math/tex" id="MathJax-Element-76">p<=\sqrt n</script>，所以<script type="math/tex" id="MathJax-Element-77">k>=\sqrt n>=p</script>，所以<script type="math/tex" id="MathJax-Element-78">s。而<script type="math/tex" id="MathJax-Element-79">\lfloor\frac{n}{p}\rfloor</script>的值就是<script type="math/tex" id="MathJax-Element-80">k</script>。

那么，就会有<script type="math/tex" id="MathJax-Element-81">\lfloor\frac{n}{\frac{n}{p}}\rfloor=\lfloor\frac{n}{k}\rfloor</script>。在此基础上，让我们再证明一个结论：<script type="math/tex" id="MathJax-Element-82">\lfloor\frac{n}{k}\rfloor=p</script>。我们令<script type="math/tex" id="MathJax-Element-83">n\div k=(p+t)...w</script>，则<script type="math/tex" id="MathJax-Element-84">n=p*k+t*k+w</script>。又因为<script type="math/tex" id="MathJax-Element-85">n=p*k+s</script>而，所以<script type="math/tex" id="MathJax-Element-86">n=p*k+t*k+w=n+(t*k+w-s)</script>，所以<script type="math/tex" id="MathJax-Element-87">t*k+w-s=0</script>。因为<script type="math/tex" id="MathJax-Element-88">k>w</script>且<script type="math/tex" id="MathJax-Element-89">k>=\sqrt n</script>，所以我们可以得出：<script type="math/tex" id="MathJax-Element-90">w,s\in[0,\sqrt n)</script>。所以：<script type="math/tex" id="MathJax-Element-91">(w-s)\in(-\sqrt n,\sqrt n)</script>。又因为<script type="math/tex" id="MathJax-Element-92">k>=\sqrt n</script>，所以<script type="math/tex" id="MathJax-Element-93">t</script>必须为<script type="math/tex" id="MathJax-Element-94">0</script>。所以<script type="math/tex" id="MathJax-Element-95">\lfloor\frac{n}{k}\rfloor=p</script>就证完了。而又由我们上面证的结论：<script type="math/tex" id="MathJax-Element-96">\lfloor\frac{n}{i}\rfloor</script>的取值总共不会超过<script type="math/tex" id="MathJax-Element-97">2\sqrt n</script>种可以知道当<script type="math/tex" id="MathJax-Element-98">p<=\sqrt n</script>的时候，所有<script type="math/tex" id="MathJax-Element-99">\lfloor\frac{n}{p}\rfloor</script>的值都不相同，即<script type="math/tex" id="MathJax-Element-100">p=i_{max}</script>。所以<script type="math/tex" id="MathJax-Element-101">i_{max}=\lfloor\frac{n}{\frac{n}{p}}\rfloor</script>，得证了。

当<script type="math/tex" id="MathJax-Element-102">p>\sqrt n</script>时：

我们设<script type="math/tex" id="MathJax-Element-103">n\div p=k...s</script>，那么就有<script type="math/tex" id="MathJax-Element-104">n=p*k+s</script>。根据除法的性质，<script type="math/tex" id="MathJax-Element-105">s。而<script type="math/tex" id="MathJax-Element-106">\lfloor\frac{n}{p}\rfloor</script>的值就是<script type="math/tex" id="MathJax-Element-107">k</script>。

那么，就会有<script type="math/tex" id="MathJax-Element-108">\lfloor\frac{n}{\frac{n}{p}}\rfloor=\lfloor\frac{n}{k}\rfloor</script>。而我们现在要证明的，就是<script type="math/tex" id="MathJax-Element-109">\lfloor\frac{n}{k}\rfloor=i_{max}</script>。看上去很难证，但是我们注意到<script type="math/tex" id="MathJax-Element-110">i_{max}</script>必须符合且只需要符合的两个条件：<script type="math/tex" id="MathJax-Element-111">\lfloor\frac{n}{i_{max}}\rfloor=\lfloor\frac{n}{p}\rfloor=k,\lfloor\frac{n}{i_{max}+1}\rfloor\not=\lfloor\frac{n}{p}\rfloor=k</script>。那么，如果我们需要证明<script type="math/tex" id="MathJax-Element-112">\lfloor\frac{n}{k}\rfloor=i_{max}</script>，那么就只需要说明<script type="math/tex" id="MathJax-Element-113">\lfloor\frac{n}{\lfloor\frac{n}{k}\rfloor}\rfloor=\lfloor\frac{n}{p}\rfloor=k\space\space and\space\space\lfloor\frac{n}{\lfloor\frac{n}{k}\rfloor+1}\rfloor\not=\lfloor\frac{n}{p}\rfloor=k</script>。看到<script type="math/tex" id="MathJax-Element-114">\lfloor\frac{n}{\lfloor\frac{n}{k}\rfloor}\rfloor=k</script>你想到了什么？

聪明的读者一定已经想到了，因为这个<script type="math/tex" id="MathJax-Element-115">k<\sqrt n</script>（讲了这么多这个不可能不会自行理解吧），所以这个结论在上面讨论<script type="math/tex" id="MathJax-Element-116">p<=\sqrt n</script>的时候已经证过了。所以，得证啦！

<script type="math/tex; mode=display" id="MathJax-Element-117">\mathcal{Q.E.D}</script>

综合上面两个结论，我们便可以得出整除分块的思路了：

  1. 令<script type="math/tex" id="MathJax-Element-118">i=1</script>

  2. 对于当前的<script type="math/tex" id="MathJax-Element-119">i</script>求得<script type="math/tex" id="MathJax-Element-120">i_{max}</script>，设为<script type="math/tex" id="MathJax-Element-121">j</script>

  3. 通过前缀和或公式（例如等差数列公式）求得函数（<script type="math/tex" id="MathJax-Element-122">\sum_{i=1}^nf(i)</script>中的<script type="math/tex" id="MathJax-Element-123">f(i)</script>）的自变量从<script type="math/tex" id="MathJax-Element-124">i</script>一直到<script type="math/tex" id="MathJax-Element-125">j</script>的函数值的总和，并且加进<script type="math/tex" id="MathJax-Element-126">sum</script>

  4. 我们已知<script type="math/tex" id="MathJax-Element-127">\lfloor\frac{n}{j}\rfloor\not=\lfloor\frac{n}{j+1}\rfloor</script>，所以我们让<script type="math/tex" id="MathJax-Element-128">i=j+1</script>。如果现在的<script type="math/tex" id="MathJax-Element-129">i</script>仍然小于<script type="math/tex" id="MathJax-Element-130">n</script>，则跳转第<script type="math/tex" id="MathJax-Element-131">2</script>步，否则结束

最终得到的<script type="math/tex" id="MathJax-Element-132">sum</script>就是答案了。

卡特兰数

递推公式1

<script type="math/tex; mode=display" id="MathJax-Element-133">a_1=1,a_i=a_1a_{i-1}+a_2a_{i-2}+...+a_{i-1}a_1</script>

定义，长为题目表面形式

递推公式2

<script type="math/tex; mode=display" id="MathJax-Element-134">a_1=1,a_i=a_{i-1}*\frac{4n-6}{n}</script>

证明：转化成实际问题求得除递推公式1外另一个复杂度较高的递推公式，综合二公式求得递推公式2（<script type="math/tex" id="MathJax-Element-135">eg.</script>多边形三角剖分问题）

组合公式 1

<script type="math/tex; mode=display" id="MathJax-Element-136">when\space i=1,a_i=1</script>

<script type="math/tex; mode=display" id="MathJax-Element-137">when\space i>1,a_i=\frac{C_{2i-2}^{i-1}}{i}</script>

证明：由递推公式2用累积法求得

组合公式 2

<script type="math/tex; mode=display" id="MathJax-Element-138">when\space i=1,a_i=1</script>

<script type="math/tex; mode=display" id="MathJax-Element-139">when\space i>1,a_i=C_{2i-2}^{i-1}-C_{2i-2}^{i-2}</script>

证明：倒推可得到组合公式1