Integer Product 解题分析
问题描述：
给出\( N \) 个数字\(A_i \)，形式可能是整数或小数，统计有多少对 \( (A_i,A_j) ( i<j ) \)的乘积\( A_i \cdot A_j \)为整数。
数据限制：
\( 0 < N \leq 200000 \)
\( 0 < A_i <10^{4} \)
\( A_i \) 若为小数则小数点后最多有9位数字
分析：
小数点后可能有9位，那么两个小数点后都是9位的数字相乘则精度会超过double允许的类型，所以可以将小数转化为分数，编写一个有理数类。对于小数\(a.b = a + 0.b \)，若小数点后的\(b\)部分的长度为\( L \) 则\(a.b\)可写为分数形式\(\frac{a \cdot 10^L+b}{10^L}\)，再编写判断两个分数相乘是否为整数就可以，遍历所有\( A_i\)以及\( i<j \)的\( A_j \) 统计数量即可。
然而这个程序给出了 AC*5,TLE*5的结果。说明此题这种\( O(N^2) \)的效率并不合格。
针对本题，转化成有理数运算的思路是正确的，但不需要使用有理数的运算，因为从小数化为分数，分数的分母都是从\(10^L\)开始，并可能被约分，最后分母只剩\(2^a 5^b \)的形式，也就是说如果要将一个数字的分母\( 2^a \cdot 5^b \)约去，只需要看这个数字的分子与另一个数字的分子之积是否含有\( 2^a \cdot 5^b \)的因子，其它的因子都不会有影响。例如\( 7.5 = \frac{75}{10} = \frac{15}{2}\)，它在本题中与\( \frac{5}{2} \)起到的作用是相同的，因为\( 15=3 \times 5 \)，但是因子\( 3 \)在分子上无论如何也不会将分母 \( 2^a 5^b \) 约去任何一部分，只有因子\(5\)有作用。
这样，在本题中，我们将每个数字用\( (a,b) \) 描述，对应于\(2^a \cdot 5^b \)。若两数相乘为整数，则两数 \(2^a \cdot 5^b \) 与 \(2^c \cdot 5^d \)的乘积是 \(2^{a+c} \cdot 5^{b+d} \)，即\((a+c,b+d) \) ，若有\( a+c \geq 0 \text{ and } b+d \geq 0 \)，则两数之积为整数。
由于小数最多有9位，即最小的数字是\( 0.000000001 \)，即\( 2^{-9}\cdot 5^{-9} \) ，最大可能为\( 10000 \) ,即\( 2^{4}\cdot 5^{4} \) 只需要一个二维数组，将相应a与b的数字数量存入数组，只需要遍历整个数组即可计算结果。或者使用map<pair<int,int>,int>结构保存，map的键是2的幂a与5的幂b组成的pair (a,b)，map对应的值为这个(a,b)所对应的数字个数。二重遍历map可以计算得到结果。Accepted的程序代码如下所示
[TABS_R id=2194]