几道有意思的题

文章目录

今天 picks 来讲课,有几道有意思的题

T1

设斐波那契数列第 $i$ 项为 $F_i$ ,求最小的 $x$ 使
$$ F_x\equiv k \pmod{1e9+9} $$
首先有一个斐波那契递推式
$$ F_i=\frac{1}{\sqrt 5}\bigg{(}\big{(}\frac{1+\sqrt 5}{2}\big{)}^i-\big{(}\frac{1-\sqrt 5}{2}\big{)}^i\bigg{)} $$

设 $a=\frac{1+\sqrt 5}{2}, b=\frac{1-\sqrt 5}{2} $ ,那么有 $ab=1$ ,那么设 $\varphi=\frac{1+\sqrt 5}{2}$ ,原方程相当于
$$\frac{1}{\sqrt 5}\big{(}\varphi ^x – \frac{(-1)^x}{\varphi ^x}\big{)} \equiv k \pmod{1e9+9}$$
化一下,然后左右乘上 $\varphi ^x$
$$ \varphi ^{2x}-\sqrt 5 k\varphi ^x – (-1)^x\equiv 0 \pmod{1e9+9} $$
可以枚举 $x$ 的奇偶性,此时方程确定下来了,根据一元二次方程通解可以将 $\varphi ^x$ 解出来,然后用 $BSGS$ 算出 $x$ ,判断是否符合之前枚举的奇偶性,更新答案

T2

给出 $a,b(a,b\leq 10^{1000})$ ,求 $gcd(F_a, F_b) \mod P$ ,其中 $F_i$ 为第 $i$ 个 $Fibonacci$ 数
有一个有关 $Fibonacci$ 数的性质,是
$$ gcd(F_i, F_j) = F_{gcd(i, j)} $$
于是对于 $a,b$ 求出 $gcd$ 然后再十进制矩阵快速幂就行了
性质的证明可以在网上找到

sys_con

高一 OIer,常规 / 竞赛都渣得不行

发表评论

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