hotpepsiの練習帳

SRM 661

21:09

https://competitiveprogramming.info/topcoder/srm/round/16464/div/1

Div1 Easy (250) MissingLCM

問題

• N+1からMまでの数の最小公倍数をAとする
• 1からMまでの数の最小公倍数をBとする
• Nが与えられたとき、A=Bとなる最小のMを求める

方針

• 1からNまでに含まれる素因数(とその累乗)が、N+1以降で必ず出現する必要がある
• その出現位置の最大値がM
• Passed System Test
• LCMに影響するのは素数とその累乗p^nで、それが次に出現するのはその数の2倍なので、2*p^nの最大値を求めればいい
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_661/MissingLCM.cpp

結果

o-- -1 +1 106.14 + 25 = 131.14pt 181st/318 rating 1351 -> 1379 (+28)

一応解けた。

2倍を求めればいい理由に納得するのに時間がかかった。

http://togetter.com/li/833709