怎樣求出K個斐波那契數的最小公倍數？

12-30

k&<=50000,f(i)中i&<=1e6.結果mod 1e9+7
幫助同學提問。

這個題前天鄙省省隊集訓剛做過，數據範圍完全相同。這個題本身就是一個出過很多很多次的原題。

首先有結論 $gcd(f_n,f_m)=f_{gcd(n,m)}$ 。這個只需要注意到 $gcd(f_n,f_m)=gcd(f_n,f_{n-m})$ 即可。

然後關於多個數的 $ext{lcm}$ ，有許多同學認為 $ext{lcm}{S}=displaystylefrac{prod S}{gcd{S}}$ ，這顯然是不對的。正確的結論應該是 $ext{lcm}{S}=displaystyleprod_{Tsubseteq S,T e ,emptyset} gcd{T}^{(-1)^{|T|+1}}$ 。這個結論可以對 $ext{lcm}$ 的每個質因子的冪進行最大最小值容斥得出。

對這個題應用這個結論，可以得到：

$egin{aligned} ext{lcm}{f_S}=prod_{Tsubseteq S,T e ,emptyset} gcd{f_T}^{(-1)^{|T|+1}}\=prod_{Tsubseteq S,T e ,emptyset} f_{gcd{T}}^{phantom{gcd{T}}(-1)^{|T|+1}}end{aligned}$

然後我們構造數列 ${g_n}$ ，使其滿足 $f_n=prod_{dmid n}g_d$ ，則有

$egin{aligned} ext{lcm}{f_S}=prod_{Tsubseteq S,T e ,emptyset} {left(prod_{dmidgcd{T}}g_d ight)}^{(-1)^{|T|+1}}\ =prod_{d}g_d^{sum_{Tsubseteq S,T e ,emptyset,d|T}(-1)^{|T|+1}} end{aligned}$

考慮 $g_d$ 指數的意義，可以得到

$displaystylesum_{Tsubseteq S,T e ,emptyset,d|T}(-1)^{|T|+1}= egin{cases} 1 left|{amid ain S,d|a} ight|>0\ 0 ext{otherwise} end{cases}$

因此有

$ext{lcm}{f_S}=displaystyleprod_{exists ain S, dmid a}g_d$

通過此式可以在 $O(nlog n)$ 時間內計算答案（ $n=max{S}$ ）。

有人問 $g_n$ 怎麼算，把定義中除了 $g_n$ 的項都移到另一邊就能得到 $g_n=f_ncdotleft(prod_{dmid n,d e n}g_d ight)^{-1}$ ，愉快的按這個式子遞推就可以了。

頂一下 @張一釗的答案。這個題目最早是在14年HackerRank的一次比賽中看到，原題範圍N &<= 1E9，K&<= 100。解法是一樣的。我做過比賽之後，覺得這個Idea很新穎，但解法不夠優雅，便修改了數據範圍，N &<= 1E6，K &<= 50000。於是有了一個與K無關的解法(nlogn)。預處理逆元後，用篩法就搞定了（不到30行代碼）。個人認為這個數據範圍的修改提升了題目的質量。雖然現在已淪為路人題，但當年這題還是很有意思的。

Fib的最小公倍數 - 51Nod ，給大家一個提交地址。

是不是這個題啊

我記得O( nlogn )搞一波就完了

=@@problem.Title 問題 - 51Nod

在LRJ的黑書上面有個結論，是 $gcd(fib(a),fib(b))=fib(gcd(a,b))$