https://atcoder.jp/contests/agc047/tasks/agc047_a
解説
https://atcoder.jp/contests/agc047/submissions/15792907
実数の積をそのまま受け取って積が整数である問題であるが、
実数の形のまま計算して、積が整数であるかを判定するのは誤差的にだいぶ怖い。
この時点で、なにか別のアプローチが必要となる。
整数に持ち込む
条件から考えてみる。
弱点を考えてみると、「A_iは小数部の桁数が9以下である」くらいしか珍しい所がない。
実数問題は整数でまずは扱えないかを考えるのが第一。
10xをかけて整数に持ち込んで整数上で計算して、小数に変換すると、場合によっては誤差ゼロになる。
今回もこのアプローチが役に立つ。
A_i * A_jであるが、どちらも109倍すれば、積は整数計算となる。
A_i * 109 * A_j * 109 / 1018
これが整数であれば、元々も整数である。
B_i = A_i * 109と考えると、B_i * B_j / 1018となり、これが整数となるには、B_iとB_jの積の因数に1018を含めばいい。
限定的な条件に帰着させた。
B_i = A_i * 109と考えるとき、B_i * B_jの因数に1018を含む組合せ。
全ペアの列挙問題は片方を全列挙してもう片方を探す
全ペアの列挙問題は片方を全列挙して、当てはまるもう片方を探せばいい。
これだと、重複して数えてしまうので、最後に答えを÷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; }