hotpepsiの練習帳

SRM 599

math | 01:54

Div1 Easy (250) BigFatInteger

問題

• LunはAのB乗のような巨大な数が大好きである
• Xの初期値を1とする
• Xには素数か、または、Xの約数をかけることができる
• AのB乗にするための最小の手数を求める

方針

• 素数については必ず1回は必要
• 素因数分解する
• 任意の約数をかけることができるので、素因数の中で乗数Cが一番多いものだけ考えればいい
• 繰り返し2乗法的な感じ
• 2^16だったら2^1 -> 2^2 -> 2^4 -> 2^8 -> 2^16と5回でいける
• B乗の部分についても繰り返し2乗法
• Failed System Test
• A^(C×B)という形になるが、乗数をC×Bでひとまとめにして2の累乗で切り上げする必要があった
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_599/BigFatInteger.cpp

Div2 Easy (250) MiniatureDachshund

問題

• みかんを食べた量だけ体重が増える
• 体重は5000グラムを超えてはならない
• 食べられる最大の個数を求める

方針

• ソートして足す
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_599/MiniatureDachshund.cpp

結果

x-- +1 -1 25pt 481st/739 rating 1439 -> 1420 (-19)

素数表まったくいらなかった。シンプルに書くの難しい。