AGC047 A - Integer Product 解いてみた - あるたいるの競プロ手記

こんにちは、あるたいるです。

AGC047 の日本語解説がまだ出ていないことと、自分とおなじ考え方をしている人が少なそうだったので、初めて解説記事を書いてみます。正直、エレガントではないですが（main関数が80行くらいある…）、非常に気持ちよく解けたので自慢させてください。かなり素直な発想が多いので、腑に落ちやすいと思います。

atcoder.jp

問題概要

$N$ 個の実数 $A_1, \ldots ,A_n$ が与えられる。積が整数になる2数のペアの個数は？

制約

$2\leq N\leq 200000$

$0\lt A_i \lt 10^4$

$A_i$ は小数部の桁数が $9$ 以下

考えたこと

まず、小数のままではいろいろとマズそうなので、文字列として受け取って何かするはず。 $10^9$ 倍すれば整数になるが、この数は最大で $10^{13}$ くらいになるから、2数の積を考えるとオーバーフローするのでなんだかやな感じ。そうすると、分母が $10^9$ である分数で表すしかない。けれど、これなら「2数の積が整数」を簡単に表現できる。

分数は全て既約分数にする（ただし分母が1のときは残す）。分母と分子のGCDで割ってやれば良い。その上で、 $\frac{b}{a} \times \frac{d}{c}$ が整数になる必要十分条件を考えると、 $a$ と $b$ 、 $c$ と $d$ が互いに素であることから、「 $a$ が $d$ の約数かつ $c$ が $b$ の約数」であることはすぐにわかる。

そうすると、分子の約数を列挙したいと思うのが自然な発想。しかし、分子は最大で $10^{13}$ である。普通に列挙すれば $A_i$ の1要素につき $\sqrt{10^{13}}$ となり、到底間に合わない。どうしよう？

ここで、これらの分数の分母は、もともと $10^9$ であったことに注目しよう。すると、分母の取りうる値はごく少ないことに気づく。すなわち、 $10^9$ の約数である！ $10^9$ の約数はたったの $100$ 個しかないので、列挙すべき分子の約数もその $100$ 個の中にあるものだけでいいのである。

それでは、 $100$ 個の分母を全探索しよう。ある $10^9$ の約数 $d$ について考える。分母が $d$ である分数 $X$ について、 $X$ とペアになる可能性があるのはどの分数か？当然、列挙した分子の約数の中に $d$ が存在する分数である。この分数は1つとは限らないが、その一つを $Y$ とする。 $X$ と $Y$ がペアになるためには、 $X$ の分子の約数の中に、 $Y$ の分母が含まれていれば良い。同じ分母を持つ分数について事前に計算をしておけば、複数の $X$ を同時に処理できる。 $Y$ は高々 $N$ 個であるので、計算量は $O(100 \times N)$ で抑えられる。