给定函数
f(i)={[i=1] i≤1a×f(i−1)+b×f(i−2) i>1f(i)=\begin{cases}[i=1]\ \ \ \ i\le1\\a\times f(i-1)+b\times f(i-2)\ \ \ \ i>1\end{cases}f(i)={[i=1] i≤1a×f(i−1)+b×f(i−2) i>1
求 gcdk=1i−1f(i−k)×bk−1\gcd\limits^{i-1}_{k=1} f(i-k)\times b^{k-1}k=1gcdi−1f(i−k)×bk−1,你只需要将这个式子变得简洁即可,即理论上 O(1)O(1)O(1) 且不存在多个 f(i)f(i)f(i) 的式子。
比如 gcd(f(i),binf)\gcd(f(i),b^{\inf})gcd(f(i),binf),但这个似乎不对。