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]に対してで分解しても間に合いそうだが、エラトステネスの篩で高速に求めることもできる。計算量がなのは間違いないけど、もっといい上界があるかもしれない。
Saiko~ No Contesuto #03 C. 歯車と箱
感想
エラトステネスの篩はやりすぎだったのかな。
*1:『数学ガール/フェルマーの最終定理』参照