AGC047 A - Integer Product (300)
最初の考察
実際に全通り計算するのは$ O(N^2)で間に合わない
小数は$ 整数 \times 10^kで表せるので、2と5が因数に何個あるのか数えれば良い
個数に応じてグループに分けて計算することで計算量を減らせる
最大で$ 10^4なので作られる範囲は$ 2^{15}から$ 2^{-13}と$ 5^5から$ 5^{-5}だろう
グループ毎に計算する時は2も5も0乗以上になっている場合のみ加算する
同じグループで掛け合わせるときは片方から自身を取り除いて計算する必要があるので注意
WA
次の考察
整数部分は$ 10^{13}までなり得るのでより大きい範囲まで考える必要がある
$ 2^{37}から$ 2^{-13}と$ 5^{20}から$ 5^{-10}までにしたらAC
$ N個それぞれで2と5が何個含まれているか計算する必要があるので$ O(N \log (\max A))