上體育課的時候,老師放了一排下圖這個東西,然後說:「我放了一些三角錐,等一下……」但你完全沒有心思去聽等一下要做什麼,因為你發現這些東西根本就不是三角錐,而是圓錐(如果忽視它上面那個洞的話)!
忿忿不平的你,決定要來破壞這一排「圓錐」。體育老師放了
為了避免被老師發現你在搞破壞,你每次都只能偷走相鄰的 2 個或 3 個圓錐。在你一次偷走的圓錐中,如果有任兩個圓錐上面寫的數字是互質的,你就會覺得很不滿意,而你偷一次圓錐的滿意度是「你這次偷的圓錐中,兩兩相鄰的圓錐上面寫的數字的最大公因數總和」。換句話說,如果你一次偷了
並且你獲得的滿足度是
在偷完一次圓錐後,體育老師會挪動一下剩下的圓錐,以避免圓錐之間有太大的間隔,但是圓錐的相對順序不會改變。
你希望把這排圓錐全部偷走,並且最大化每次偷圓錐的滿足度總和。
第一行有一個整數
第二行有
輸出一個整數,表示你偷完圓錐後,每次偷圓錐的滿足度總和最大值。如果你不可能偷完所有圓錐,輸出
對於第一筆範測,你可以先偷走第
2021 師大附中校隊培訓 模擬競賽
From NTU ADA 2021 Fall HW2
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~3 | 範例測資 | 0 |
2 | 4~17 | 9 | |
3 | 18~23 | 11 | |
4 | 4~17, 24~36 | 31 | |
5 | 0~47 | 無額外限制 | 49 |