P3986 斐波那契数列(扩欧求逆元)

· · 题解

思路

当我刚开始看到这个题的时候，还没有什么思路，但是当我列出了几个关于 a,b,k 的式子：

a+b=k,a+2b=k,2a+3b=k,3a+5b=k\dots

可能还不太明显，仔细观察 a,b 的系数，可以发现，这不就是斐波那契数列吗！！！

那么我们设 f(x) 为斐波那契数列的第 x 项，那么可以转化为：

f(0)*a+f(1)*b=k,f(1)*a+f(2)*b=k f(2)*a+f(3)*b=k\dots f(x-1)*a+f(x)*b=k

那么我们就可以枚举 x 。

然后，移项，可得：

b=\dfrac{k-f(x-1)*a}{f(x)}

由于 b 为整数，所以相当于求多少 a 可以使得 f(x)|k-f(x-1)*a 成立，即：

k-f(x-1)*a\equiv 0~(mod~f(x)) f(x-1)*a\equiv k~(mod~f(x)) a\equiv k*inv(f(x-1))~ (mod~f(x))

由于 f(x) 和 f(x-1) 互质（这里就不证明了），可以直接扩欧干上去求逆元，然后差不多了

（小trick：因为 k-f(x-1)*a>0 即 a<\dfrac{k}{f(x-1)}，所以可以枚举的更少了）