CF1264F Beautiful Fibonacci Problem

一道比较Beautiful的结论题，初始感觉难以下手，做了后认为在CF3500中不算很难的（逃

看到题目中“后18位的子串”,很明显的，我们要求一下Fibonacci数列 ${mod}10^k$ 的循环节。
实践打表证明这个循环节为 $1.5*10^k$

但是我们需要一个随Fibonacci下标线性增加，$mod10^k$ 的值也线性增加的方法，而如果下标每次加循环节，模出的值是相同的。为了产生这个线性增长的公差，考虑用大的模数模小的循环节

观察Fibonnaci的诸多性质，在模数增加后仍能存在性质的只有对Fibonacci数列的平方，即 $Fib_{2n+1}=Fib_{n+1}^2+Fib_{n}2$ 。于是想到对模数也平方，设循环节为 $N$ 就得到了一个很好的式子：

$Fib_{N+1}≡t10^k+1(mod 10^{{2k}),Fib_{2N+1}=Fib_{N+1}}2+Fib_{N}^2≡(t+1)2≡2t10^k+1(mod 10^{2k})$

这样就能归纳得到 $Fib_{xN+1}≡xt*10^k+1(mod10)$，就是上面说的我们想要得到的式子。

然后就是我卡住的地方。因为我们只需要等差数列 ${a_n}$ 中的数只需在其子串中出现，于是只需让 $a+id≡xt(mod10^k)$ 就能满足条件。因为 $t$ 和 $10^k$ 是互质的，所以 $t$ 关于 $10^k$ 是有逆元的，只需用exgcd就能求出

于是$xN+1≡aNt^{-1}+1+dN*ti$，即得到 $b=Nat^{{-1}+1,e=N*d*t}$。注意最后要对 $a*t^{-1},b*t$ 取模，而 $N$ 是循环节，不要取模

于是，我们就愉快的把这道3500 constructive algorithms 秒了(bushi

代码就不贴了，过于简单。因为 $a_n$ 最大不超过 $10^6$ ，于是模数选 $10^6-109$ 都可以。我为了省去矩阵快速幂，选了 $10^7$ ，此时 $t^{-1}=9945049$

完结撒花！