[题解]斐波那契的最小公倍数 Max-Min 容斥+莫比乌斯反演 51nod1355  -  - litble
于 2018年12月24日 由litble发布
首先有一个结论:$gcd(fib(a_i))= fib(gcd(a_i))$,可以尝试使用辗转相减球 gcd 的方法证明一下.(boshi: 可以证,但没必要)
然后 $lcm$是个什么玩意呢?对于一个指定的质因数 $p$,假设 $a_i$的质因数 $p$的次数为 $c_i$,则他们的 lcm 的 $p$的次数为 $max(c_i)$,gcd 的 $p$的次数为 $min(c_i)$.看到这里,可以考虑 Max-Min 容斥(又称 Max-Min 反演),最后可以得到