Hints

Idea

If we express every \(A_i\) as irreducible fraction, e.g. \(7.5 = \frac{75}{10} = \frac{15}{2}\), the denominator must be of form \(2^a \cdot 5^b\). When checking if product of two numbers is integer, it’s enough to check if powers of \(2\) and \(5\) are reduced. So number \(\frac{15}{2}\) can be replaced with \(\frac{5}{2}\) and the answer won’t change. So we just need to deal with numbers like \(\frac{5}{2}\), \(\frac{8}{125}\) or \(40 = 2^3 \cdot 5^1\).

Solution

Represent every \(A_i\) as \(2^a \cdot 5^b\). For example, \(7.5 = \frac{15}{2} = 2^{-1} \cdot 5^1\), we skip the part non-divisible by \(2\) and \(5\).

Let \(cnt[a][b]\) be the number of elements \(A_i\) that are equivalent to \(2^a \cdot 5^b\). Iterate over every pair of pairs \((a,b)\) and \((a', b')\) and check if \(a + a' \geq 0\) and \(b + b' \geq 0\). If yes, add \(cnt[a][b] \cdot cnt[a'][b']\) to the answer. The code below shows how to avoid double counting.
Values \(a\) and \(b\) are in range \([-9, 30]\) (e.g. consider \(A_i = 2^{30} \cdot 5^{-9}\)) but you can do \(a=min(a,9)\) and \(b=min(b,9)\).

Alternatively, multiply \(A_i\) by \(10^9\) and deal with a convenient form of \(\frac{x}{10^9}\) for integer \(x\). If \(x = 2^a \cdot 5^b\), you’re looking for pairs such that \(a+a' \geq 18\) and \(b+b' \geq 18\).

Let \(L = \log(10^{13})\). The time complexity is \(O(N \cdot L + L^4)\) or \(O(N \cdot L^2)\) if you count pairs as you go through the input: for(A[i]) { compute a, b; for(previous_a) for(previous_b) if(a+previous_a >= 18 && ...) ... }

Preacision and Reading Input

While it might seem safer to read a string and parse it yourself, it’s enough to read a real value, multiply by \(10^9\) and round to integer. In C++, that’s double x; cin >> x; long long y = llround(x * 1e9);

In most languages (e.g. C++ and Python), basic double type has 53 bits of precision and that’s enough to precisely represent integers up to \(2^{53}\) which is greater than \(10^{13}\).

#include <bits/stdc++.h> // Integer Product, by Errichto
using namespace std;
int main() {
	int n;
	scanf("%d", &n);
	map<pair<int,int>, int> cnt;
	for(int rep = 0; rep < n; ++rep) {
		double x;
		scanf("%lf", &x);
		long long i = llround(x * 1e9);
		int two = 0, five = 0;
		while(i % 2 == 0) {
			two++;
			i /= 2;
		}
		while(i % 5 == 0) {
			five++;
			i /= 5;
		}
		++cnt[{two,five}];
	}
	long long answer = 0;
	for(auto p1 : cnt) {
		for(auto p2 : cnt) {
			if(p1.first.first+p2.first.first >= 18 && p1.first.second+p2.first.second >= 18) {
				if(p1 < p2) {
					answer += (long long) p1.second * p2.second;
				}
				else if(p1 == p2) {
					answer += (long long) p1.second * (p1.second - 1) / 2;
				}
			}
		}
	}
	printf("%lld\n", answer);
}