YZOJ P4587 斐波那契数列

YZOJ P4587 斐波那契数列

时间限制:1234MS      内存限制:43210KB

难度:\(6.5\)       (既然是自己搬的题还是正常一点吧w)

  • 题目描述

定义模意义下的递推数列 \(f_n=\left\{ {\begin{array}{*{20}{c}} 1&{,n \le 2}\\ {{f_{n – 1}} + {f_{n – 2}}}&{,n > 2} \end{array}} \right.\),其中模数为 \(1000000009\) 。

给定整数 \(c\)(\(0 \leq c < 1000000009\)),求出它最早出现在数列的哪个位置,并输出下标。

若 \(c\) 永远不会出现在此数列的任一位置,则输出 \(-1\) 。

  • 输入格式

多组数据。

第一行一个正整数 \(T\) (\(0 < T \leq 100\)) 表示 \(T\) 组数据。

接下来 \(T\) 行每行一个数表示每组数据的 \(c\) 。

  • 输出格式

对于每组数据,输出一行一个数表示答案。

  • 样例输入

  • 样例输出

 

 

 

Source: BZOJ 5104


 

 

 

在其他地方偷偷藏了点私货www,然而这里没有(不需要藏)

 

简约概述:有公式 \(f_n=\frac{1}{\sqrt5}\left(\frac{1+\sqrt5}{2}\right)^n – \frac{1}{\sqrt5}\left(\frac{1-\sqrt5}{2}\right)^n\) ,可以套用 BSGS 以及 Cipolla 解出 \(n\) 。

极致内容:

  • Section A

首先,\(f_n\) 的通项公式可以通过简单的数学构造得到。

因为一阶线性常系数齐次递推的通项公式为等比数列,所以同理设 \(t, q\),使得 \(f_n-tf_{n-1} = q\left(f_{n-1}-tf_{n-2}\right)\) 。

展开整理得 \(f_n = \left(q+t\right)f_{n-1}-qtf_{n-2}\) ,即 \(\left\{ {\begin{array}{*{20}{c}}{q + t = 1}\\{qt =  – 1}\end{array}} \right.\) 。

构造二次函数 \(x^2-x-1=0\) ,由韦达定理可知 \(q, t\) 分别为此方程两根,即 \(\frac{1+\sqrt5}{2}\) 或 \(\frac{1-\sqrt5}{2}\) 。

然后套很多个等比数列求和公式,或者直接设 \(f_n = ax_1^n + bx_2^n\) 代入特殊值解方程组,都可以得出 \(f_n=\frac{1}{\sqrt5}\left(\frac{1+\sqrt5}{2}\right)^n – \frac{1}{\sqrt5}\left(\frac{1-\sqrt5}{2}\right)^n\) 。

 

  • Section B

接下来对这个公式进行一点处理。

设 \(c=f_n\),\(t=\frac{1+\sqrt5}{2}\) ,则可知 \(\frac{1-\sqrt5}{2} = -\frac{1}{t}\) ,所以有: \(\sqrt 5 c = {\left( t \right)^n} – {\left( { – {1 \over t}} \right)^n}\) 。

换元,再设 \(x=t^n\) ,则有: \(\sqrt 5 c = x – {\left( { – 1} \right)^n}\frac{1}{x}\) 。

再整理,可得以 \(x\) 为主元的一元二次方程 \(x^2 – \sqrt5cx – {\left( { – 1} \right)^n} = 0\) 。

此方程 \(\Delta = 5c^2 + 4\left( { – 1} \right)^n\) ,然后套用一元二次方程求根公式可得 \(x=\frac{{\sqrt 5 c \; \pm \sqrt \Delta  }}{2}\)

公式中其中涉及到 \(\sqrt \Delta\) 的部分,可以采用 Cipolla 求解。

其中 \(\left(-1\right)^n\) 可以根据 \(n\) 的奇偶性分成 \(-1\) 和 \(1\) 两种取值,分类讨论。

又因为 \(t^n = x\) ,所以跑 BSGS 求出 \(n\) 的最小正整数解,并与其他情况求出的 \(n\) 取最小即可得出答案。

 

  • Section C

会 BSGS 的人可以去 AC 了。

BSGS (Baby-step giant-step) 是求解模意义下方程 \({a^x} \equiv b\pmod p\) (这里假设 \(p\) 为质数)中 \(x\) 的最小正整数解的一种方法。

首先,最小正整数解 \(x\) 不会超过 \(p-1\) 。

若 \(x \geq p\) ,那么可以设 \(x=i\left(p-1\right)+j\) ,其中 \(i \geq 1, 0 \leq j < p-1\) 。

那么有 \({a^x} = {a^{i\left(p-1\right) + j}} = {a^{i\left(p-1\right)}}{a^j} \equiv b\pmod p\) 。

因为 \(p\) 为质数,\(a < p\) ,所以由费马小定理得 \(a^{p-1} \equiv 1\pmod p\) 。

所以有 \({a^x} = {a^{ip}}{a^j} \equiv {a^j} \equiv b\pmod p\) ,即 \(a^x \equiv a^{x \bmod \left(p-1\right)} \pmod p\) 。

所以只需要在 \((0, p-1]\) 内寻找 \(x\) 即可。

暴力枚举不现实,尝试将 \(p\) 分成两部分,即设 \(s=\lceil \sqrt p \rceil\),那么 \(x\) 可以分解为 \(is-j\) ,其中 \(0 < i \leq s, 0 \leq j < s\) 。

那么有 \({a^x} = {a^{is – j}} \equiv b\pmod p\) ,即 \({a^{is}} \equiv b{a^j}\pmod p\) 。

枚举 \(j\) ,把等号右边的值存到 hash_table(\(O(1)\)) 或 std::map (\(O(\log s)\))中,然后枚举 \(i\) 配对。

因为 \(i, j\) 最多只到 \(s=\lceil \sqrt p \rceil\) ,所以复杂度为 \(O(\sqrt p)\) 或 \(O(\sqrt p \log p)\)。

 

  • Section D

会 Cipolla 的人可以去 AC 了。

Cipolla 是一种求解二次剩余的高效算法。

虽然求解二次剩余也可以使用 BSGS,但是使用 Cipolla 时间复杂度会比之优秀(也不知道我能不能成功卡掉)

对于奇质数 \(p\) 及整数 \(n\),若存在整数 \(x, 0 \leq x < p\) 且满足 \(x^2 \equiv n\pmod p\) ,那么 \(n\) 就称作在模 \(p\) 意义下的二次剩余。

定义数域 \(\mathbb {F}_p\) 包含 \([0, p-1]\) 中的整数,其中的运算均在模意义下进行。若无特殊说明,下列操作均在 \(\mathbb {F}_p\) 下进行。

先来证明几个引理。

\(Lemma.1\):对于方程 \(x^2 \equiv n \pmod p\) ,总共只有 \(\frac{p-1}{2}\) 个 \(n\)(\(0<n<p\)) 使得 \(x\) 有解。

\(Proof\):假设存在两个不同的数 \(u, v\) 使得 \(u^2 \equiv v^2 \pmod p\) ,那么有 \(p\; |\; \left(u^2-v^2\right)\) ,即 \(p\; |\; \left(u+v\right)\left(u-v\right)\) 。

由于 \(p\; \not |\; \left(u-v\right)\),所以 \(p\; |\; \left(u+v\right)\) ,即 \(u+v \equiv 0 \pmod p\) 。

所以 \((0,p-1]\) 中 \(x^2 \equiv \left(p-x\right)^2 \pmod p\),有且只有 \(\frac{p-1}{2}\) 对这样的数,所以有且只有 \(\frac{p-1}{2}\) 种不同的 \(n\),得证。

\(Lemma.2\):定义 勒让德符号 (Legendre symbol) \(\left(\frac{a}{p}\right)=\begin{cases}1,&a\text{在模$p$意义下是二次剩余}\\-1,&a\text{在模$p$意义下是非二次剩余}\\0,&a\equiv0\pmod p\end{cases}\)

然后有 \(\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod p\) (即 欧拉判别法 (Euler’s criterion))。

\(Proof\):当 \(a\) 在模 \(p\) 意义下是二次剩余,即 \(\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}} \equiv 1\pmod p\) 时:设 \(x^2 \equiv a\pmod p\) ,所以有 \(x^{p-1} \equiv a^{\frac{p-1}{2}} \equiv 1\pmod p\)

根据费马小定理可知这样的 \(x\) 存在,故原命题得证。

当 \(a\) 在模 \(p\) 意义下不是二次剩余,即 \(\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}} \equiv -1\pmod p\) 时:设 \(x^2 \equiv a\pmod p\) ,所以有 \(x^{p-1} \equiv a^{\frac{p-1}{2}} \equiv -1\pmod p\)

根据费马小定理可知这样的 \(x\) 不存在,故原命题得证。

\(\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}} \equiv 0\pmod p\) 时:显然。

由于这个算法构造巧妙,所以先介绍其实现方法。

1,给定 \(n\) ,若 \(\left(\frac{n}{p}\right) \neq 1\) ,则可以直接给出答案。

2,随机 \(a\) 直到 \(\left(\frac{a^2-n}{p}\right) = -1\) 。由 引理1 可知,期望随机次数为 \(2\)。

3,扩展至 \(\mathbb{F}_{p^2}\),并把 \(\sqrt{a^2-n}\) 作为“第二条数轴”的单位长度(可类比复数)。这样,此域中的数可以表示为 \(a+b\omega\) ,其中 \(\omega^2 = a^2-n\) ,并且此数域依然满足交换律、结合律以及分配律。

Q:为什么贴图?   A:因为我看不懂

 

4,将 \(x\) 也扩展至 \(\mathbb{F}_{p^2}\),\(x \equiv \left(a+\omega\right)^{\frac{p+1}{2}} \pmod p \) ,取 \(x\)“第一条数轴”中的部分即为答案。

要证明或者搞懂这个是在说什么,还需要再证明一些引理。

\(Lemma.3\)\(\omega^p \equiv – \omega \pmod p\)

\(Proof\)\({\omega ^p} \equiv \omega  \cdot {\omega ^{p – 1}} \equiv \omega {\left( {{\omega ^2}} \right)^{\frac{{p – 1}}{2}}} \equiv \omega {\left( {{a^2} – n} \right)^{\frac{{p – 1}}{2}}} \equiv  – \omega \pmod p\)

\(Lemma.4\)\(\left(a+b\right)^p \equiv a^p+b^p \pmod p\)

\(Proof\):根据二项式定理展开,有 \(\left(a+b\right)^p \equiv \sum\limits_{i=0}^pC_p^ia^ib^{p-i} \pmod p\) ,由于当 \(0<i<p\) 时 \(C_p^i \equiv 0 \pmod p\),所以得证。

现在已经可以来证明「步骤4」了。

根据叙述,已知 \(x \equiv \left(a+\omega\right)^{\frac{p+1}{2}} \pmod p\),即 \(x^2 \equiv \left(a+\omega\right)^{p+1} \pmod p\) 。

根据 引理4 ,有 \(\left(a+\omega\right)^{p+1} \equiv \left(a+\omega\right)\left(a+\omega\right)^p \equiv \left(a+\omega\right)\left(a^p+\omega^p\right) \pmod p\) 。

根据费马小定理 \(a^p \equiv a \pmod p\) 以及 引理3,可得 \(\left(a+\omega\right)\left(a^p+\omega^p\right) \equiv \left(a+\omega\right)\left(a-\omega\right) \pmod p\) 。

所以有 \(x^2 \equiv \left(a+\omega\right)\left(a-\omega\right) \equiv a^2-\omega^2 \equiv a^2-\left(a^2-n\right) \equiv n \pmod p\) ,可证 \(x\) 为此方程的一个合法解。

等等,刚刚「步骤4」里不是说「取 \(x\)“第一条数轴”中的部分即为答案」吗?上面的证明都是在 \(\mathbb{F}_{p^2}\) 中进行的,怎么能直接取其中的一部分(保证解可以被压缩到 \(\mathbb{F}_{p}\))?

这里就要提到神奇的 拉格朗日定理 (Lagrange’s theorem) ,都知道 \(n\) 次方程最多有 \(n\) 个解,同时这个结论在模意义下仍是成立的。

所以在 \(\mathbb{F}_{p}\) 中,且 \(n\) 为模 \(p\) 意义下的二次剩余时,方程 \(x^2 \equiv n \pmod p\) 即 \(x^2-n \equiv 0 \pmod p\) 最多存在两根 \(x_0, x_1 \in \mathbb{F}_{p}\) 。

由拉格朗日定理可知即使扩展到 \(\mathbb{F}_{p^2}\) ,此方程仍然最多只会有两个根,并且这两根就“相当于是”原来的 \(x_0, x_1\),所以这两根一定可以被压缩到 \(\mathbb{F}_{p}\) 中,即 \(a+b\omega\) 中 \(b=0\) 。

(可类比复数运算/开根)

最后,分析过程可知此算法时间复杂度可近似于 \(O(\log p)\) 。

 

  • Section ?

本题总时间复杂度为:\(O\left( \sqrt p + \log p \right)\)。

涉及算法:BSGS + Cipolla + Time constant

// std::map 或者多个 log 或者哪里常数比较大都会被卡掉

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注