https://sugarknri.hatenablog.com/entry/2021/02/11/155120

a[i]=a[i-1]-a[i-2]の特性方程式が1の6乗根だからmod6で見れる、なるほどなぁという気持ちに
— TKO (@tko919_) 2021年2月10日

ほんまか？

$a_{n}=a_{n-1}-a_{n-2}$ は $a_{n}=a_{n-6}$ を満たすので、mod 6で見たいという気持ちで式変形をすると
$a_n\\ = a_{n-1} a_{n-2}^{-1}\\ = a_{n-2} a_{n-3}^{-1} a_{n-2}^{-1} \\ = (a_{n-4} a_{n-5}^{-1} a_{n-4}^{-1}) (a_{n-5} a_{n-6}^{-1} a_{n-5}^{-1})^{-1} (a_{n-4} a_{n-5}^{-1} a_{n-4}^{-1})^{-1}\\ =(a_{n-4} a_{n-5}^{-1} a_{n-4}^{-1} a_{n-5}) a_{n-6} (\ldots)^{-1}$
となって
$a_{n-4} a_{n-5}^{-1} a_{n-4}^{-1} a_{n-5}\\ =(a_{n-5} a_{n-6}^{-1}) a_{n-5}^{-1} (a_{n-5} a_{n-6}^{-1})^{-1} a_{n-5}\\ = a_{n-5} a_{n-6}^{-1} a_{n-5}^{-1} a_{n-6}\\ = a_1 a_0^{-1} a_1^{-1} a_0 =:X$
として
$a_n = X a_{n-6} X^{-1}$
を得る。よって $O(N\log K)$ で解けた。

ところでなんでこれうまくいくんすかね。

例えば $a_{n}=a_{n-1}a_{n-2}^{-1}a_{n-3}a_{n-4}^{-1}$ で同じ問題を考えると、同様にある定数 X により $a_{n}=X a_{n-10} X^{-1}$ と書けるが、途中の計算は違っていて、例えば $a_{n}=X(n) a_{n-5}^{-1} X(n)^{-1}$ とは書けない。

証明or反例を募集しています

20250226追記

@sugarknri
最後の「例えば a[n] = a[n-1] a[n-2]^{-1} a[n-3] a[n-4]で同じ問題を考えると...」という式は、一般に成り立ちます。試してませんが、記事の証明で出来るのではと（自分は画像のようにしました）。https://t.co/ERKtvoRay2 pic.twitter.com/ORMnfPc9cM
— 37zigen (@37zigen) 2025年2月25日

$a_1 a_0^{-1} a_1^{-1} a_0$ のまま考えてしまったのが才能ナシで、 $a_3 a_0$ と書くと一般のケースが証明しやすいという話だったらしい。
一般に漸化式 $a_n=a_{n-1}a_{n-2}^{-1}\ldots a_{n-2d}^{-1}$ で定まる数列を考える。
$X(n):=a_n a_{n-2d-1}$ とおく。漸化式から任意の n で $a_n^{-1} a_{n-1} a_{n-2}^{-1}\ldots a_{n-2d}^{-1}=\mathrm{id}$ であることに注意して
$X(n) =a_n (a_{n-1}^{-1} a_{n-2} a_{n-3}^{-1}\ldots a_{n-2d-1}^{-1}) a_{n-2d-1}\\ =a_n a_{n-1}^{-1} a_{n-2} a_{n-3}^{-1}\ldots a_{n-2d}\\ =a_{n+1}a_{n-2d}=X(n+1)$
より、 X(n) は n によらない定数。これを改めて X とおき $a_n = X a_{n-2d-1}^{-1} = X a_{n-4d-2} X^{-1}$ を得る。