AtCoder Grand Contest 047

AtCoder Grand Contest 047

A. Integer Product

给定 \(n\) 个浮点数，计算有多少个 \((i, j)\) 使得 \(A_{i} \cdot A_{j}\) 是整数

\(2\leq N \leq 200 \ 000\) , $ 0 < A_{i} ^{4}$ , \(A_{i}\) 最多 \(9\) 为小数.

思路

通过题设条件缩小范围， 枚举

由于数据比较大，不能直接暴力做。判断是整数这个条件不太好集体维护。所以要找出题目中的特性，看看有没有机会让范围缩小。最好是可以 先考虑 \(A_{i} \cdot A_{j}\) 什么情况下是整数。发现，对于任意有限小数 \(x\), 可以在乘上 \(10^{n}\) 后肯定会变成整数。所以每个数必然是 \(k\cdot 2^{m}\cdot 5^{n}\) 的形式, 通过乘 \(10^{n}\) 把分母上的 \(2^{m}\cdot 5^{n}\) 约去. 而之前的 \(k\) 不影响答案。所以我们只要考虑 \(2^{m}\cdot 5^{n}\) 的数即可. 由于只有 \(9\) 位. 所以最多乘以 \(10^{9}\) ，也就是 \(m, n \geq -9\). 上限也不会很高。所以可以暴力枚举. 先用哈希表确定范围，然后在枚举哈希表中的数即可. 具体参见代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
typedef long long ll;

int n;
double A[maxn];
ll B[maxn];

int main() {
    cin >> n;
    map<pair<int, int>, int> cnt;
    for (int i = 1;i <= n; ++i) {
        cin >> A[i];
        A[i] *= 1e9;
        B[i] = llround(A[i]);

        int two = 0, five = 0;
        while (B[i] % 2 == 0) two++, B[i] /= 2; 
        while (B[i] % 5 == 0) five++, B[i] /= 5; 
        cnt[{two, five}] ++;
    }
    ll ans = 0;
    for (auto p1 : cnt) 
        for (auto p2 : cnt) 
            if (p1.first.first-9 + p2.first.first-9 >= 0 && p1.first.second-9 + p2.first.second-9 >= 0) {
                if (p1 < p2) ans += (ll) p1.second * p2.second;
                else if (p1 == p2) ans += (ll) p1.second * (p1.second - 1)/2;
            }
    cout << ans << endl;
    return 0;
}