這題要利用到一些數論

因為石頭最多100

那麼中間距離將可以縮減

可是要怎麼縮減呢

利用a b兩數互質 則超過LCM(a, b)皆可被組成

但是你要怎麼知道是不是有互質的兩數

你會發現S T組成連續的interval

也就是說 利用輾轉相除法的事實 a a+1兩數必互質

因此只要S != T 則都可以組成超過該lcm的位置

這樣的話

就可以縮減兩石頭距離

也就是說長度超過九十（9 10為最大的該範圍lcm）

就可以n % 90 + 90

不過我這邊取100 但我試過90也是可以AC的

 

http://nopaste.csie.org/7bc48

arrow
arrow
    全站熱搜

    robertanders 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄