Hatena::Grouptopcoder

hotpepsiの練習帳

2014-07-30

SRM 628

01:00

Div1 Easy (250) DivisorsPower

問題

  • 数Nの約数の総数をd(N)とする
  • Nのd(N)乗をh(N)とする
  • 数nが与えられる
  • h(X) = NとなるXの最小値を求める

方針

  • 賢い解きかたがわからん
  • とりあえず因数分解して全部試すことに
  • Nの最大値が10^18で、普通に10^9まで因数分解のループを回すとTLEで死ぬ
  • 約数の最小個数は2で、Nは少なくとも2乗された数である
  • 合成数は少なくとも3乗になるが、その場合には10^6まで因数分解しておけばよい
  • 10^6までに素因数がないとき、Xが合成数だと3乗以上で10^18を超えるので、素数の2乗だけが候補となる。X=sqrt(X)として、Xの2乗がNに一致したらXは素数かつ答えで、そうでないときは解なし
  • とりうる素因数を1から試してNに一致するか調べる
  • powを使ったらX=105で誤差死したので、愚直に乗算するようにして再提出
  • Passed System Test
  • 因数分解から全探索に書き直した
  • https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_628/DivisorsPower.cpp

Div1 Medium (500) CircuitsConstruction

問題

  • いくつかの抵抗がある
  • 抵抗は組み合わせAまたはBで結合する
  • Aは和、Bは最大値
  • 組み合わせ方と使用可能な抵抗値の一覧が与えられる
  • 構成可能な抵抗値の最大値を求める

方針

結果

o-- +1 75.00 + 50 = 125.00pts 383rd/633 rating 1537 -> 1520 (-17)

約数の個数の小さい順に、(1)素数=2(2)素数の2乗=3(3)素因数が2つの合成数=4で、(1)だとsqrt(N)を調べればよく、(2)だとNの6乗根だけ調べればよく、(3)は10^18の4乗根で32000くらいまで素因数分解すればよかったらしい。

因数分解しないときはオーバーフローチェックが必要。

チャレンジケース見ていたら、書き方によっては10^9のループでも死なない場合があるようだった。

http://togetter.com/li/696518

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20140730