[WC2021] 斐波那契

T1 : 发现能到达的点为一个团,并查集&bfs 维护。

T2 : \(m\le 10\) ,一个状压的 trick 。


T3 (斐波那契)

其中一步的式子:

\(af_{i-1} \equiv bf_i \pmod m\) ,其中,\(\gcd(a,b,m)=1,\gcd(f_{i-1},f_i)=1\) ,最小化 \(i\)

\(af_{i-1} \bmod m\)\(\gcd(a,m),\gcd(f_{i-1},m)\) 倍数

\(bf_{i} \bmod m\)\(\gcd(b,m),\gcd(f_{i},m)\) 倍数

由于相等,推出:

\(bf_{i} \bmod m\)\(\gcd(a,m),\gcd(f_{i-1},m)\) 倍数

\(\gcd(a,m)|bf_i,\gcd(b,m)|af_{i-1}\)

由于上面的 \(\gcd(a,b,m)=1,\gcd(f_{i-1},f_i,m)=1\)

\(\gcd(a,m)|f_i,\gcd(f_i,m)|a \to \gcd(a,m)|\gcd(f_i,m) \& \gcd(f_i,m)|\gcd(a,m)\)

于是 \(\gcd(a,m)=\gcd(f_i,m)\) 就能往下做了。

$$\Huge \text{Goodbye OI}$$
原文地址:https://www.cnblogs.com/Rainbowsjy/p/14453530.html