Saiko~ No Contesuto #03 C. 歯車と箱

問題文

https://www.hackerrank.com/contests/camypapercon03/challenges/gear-and-box

解法

zをソートして、前半n/2個を分母に、後半n/2個を分子に持っていくと最大値になる。しかし単純に積を求めるとオーバーフローが避けられない。そこで素数指数表現*1を用いる。このようにすると自然数の積はベクトルの和に、商はベクトルの差に変換できる。
たとえば$15=2^03^15^1=[0,1,1]$と$6=2^13^15^0=[1,1,0]$の積は$15\cdot6=2^13^25^1=[1,2,1]$。

素数指数表現に変換するには素因数分解をする必要がある。これは各z[i]に対してO(\sqrt{n})で分解しても間に合いそうだが、エラトステネスの篩で高速に求めることもできる。計算量がO(n\log n)なのは間違いないけど、もっといい上界があるかもしれない。

Saiko~ No Contesuto #03 C. 歯車と箱

感想

エラトステネスの篩はやりすぎだったのかな。