SRM 713
Single Round Match 713 - Round 1:
http://community.topcoder.com/stat?c=round_overview&er=5&rd=16882
Single Round Match 713 - Round 1, Division 1:
続きを読む
- masashinakata
- 1934
- 0
- 0
- 0
nmnmnmnmnmnmnm
@enuemuenuemuenu
1の場合は先に全部やっておく。(x^i)^k = (x^j)^l(ただしl<k) としてx<32000,i<31,j<31を全探索してkがnを越えなければ答えを加算でいいがgcd(j,k)!=1のときは省く、でACしました。
2017-04-27 11:57:34
nmnmnmnmnmnmnm
@enuemuenuemuenu
2^Nが1000000000を越えないことを調べるオーダーがO(N)しか浮かばないのですが、何かありますでしょうか?
2017-04-27 12:04:52
nmnmnmnmnmnmnm
@enuemuenuemuenu
divisorとかgcdとかについての知見があるとだいぶ強くなれるというのはだいぶ前から思っていたのだけれど。
2017-04-27 12:08:17
はむこ
@hamko_intel
@enuemuenuemuenu これはクソリプですが、2^29=536870912が1e9を超えず、2^30=1073741824が1e9を超えるので、n>=30?"YES":"NO"としてO(1)で答えられます
2017-04-27 12:31:28