Integer Product [AtCoder Grand Contest 047 A]

https://atcoder.jp/contests/agc047/tasks/agc047_a

解説

https://atcoder.jp/contests/agc047/submissions/15792907

実数の積をそのまま受け取って積が整数である問題であるが、
実数の形のまま計算して、積が整数であるかを判定するのは誤差的にだいぶ怖い。
この時点で、なにか別のアプローチが必要となる。

整数に持ち込む

条件から考えてみる。
弱点を考えてみると、「A_iは小数部の桁数が9以下である」くらいしか珍しい所がない。
実数問題は整数でまずは扱えないかを考えるのが第一。
10^xをかけて整数に持ち込んで整数上で計算して、小数に変換すると、場合によっては誤差ゼロになる。

今回もこのアプローチが役に立つ。
A_i * A_jであるが、どちらも10⁹倍すれば、積は整数計算となる。
A_i * 10⁹ * A_j * 10⁹ / 10¹⁸
これが整数であれば、元々も整数である。
B_i = A_i * 10⁹と考えると、B_i * B_j / 10¹⁸となり、これが整数となるには、B_iとB_jの積の因数に10¹⁸を含めばいい。

限定的な条件に帰着させた。
B_i = A_i * 10⁹と考えるとき、B_i * B_jの因数に10¹⁸を含む組合せ。

全ペアの列挙問題は片方を全列挙してもう片方を探す

全ペアの列挙問題は片方を全列挙して、当てはまるもう片方を探せばいい。
これだと、重複して数えてしまうので、最後に答えを÷2すること。

B_iを固定したときに条件を満たすB_jを高速に探したいが、これは2と5の素因数の個数を覚えておけばいい。
例えば、B_iに含まれる2の個数がp2_i個、5の個数がp5_i個であるなら、
B_jに含まれる2の個数が18-p2_i個以上、5の個数が18-p5_i個以上であるものを探せばいい。
これはすべての数において、2の個数、5の個数は100個に満たないので、
cnt[i2][i5] := 素因数分解したときに2の個数がi2個、5の個数がi5個であるBの個数
これを事前計算しておけば、個数を全列挙して探しても間に合う。
///////////////////////// writeup2 end *

int N;
int p2[201010], p5[201010];
int cnt[60][30];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    
    rep(i, 0, N) {
        string s; cin >> s;

        ll x = 0;
        bool f = false;
        int rest = 9;
        fore(c, s) {
            if (c != '.') {
                x = x * 10 + c - '0';
                if (f) rest--;
            }
            else f = true;
        }
        rep(j, 0, rest) x *= 10;

        while (x % 2 == 0) x /= 2, p2[i]++;
        while (x % 5 == 0) x /= 5, p5[i]++;
    }
    rep(i, 0, N) cnt[p2[i]][p5[i]]++;

    ll ans = 0;
    rep(i, 0, N) {
        int need2 = max(18 - p2[i], 0);
        int need5 = max(18 - p5[i], 0);
        rep(i2, need2, 60) rep(i5, need5, 30) ans += cnt[i2][i5];
        if (need2 <= p2[i] && need5 <= p5[i]) ans--;
    }
    ans /= 2;
    cout << ans << endl;
}