A - Integer Product
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N 個の実数 A_1, A_2, \ldots, A_N が与えられます。添字のペア (i, j) (i < j) であって、積 A_i \cdot A_j が整数であるようなものの個数を求めてください。
制約
- 2 \leq N \leq 200\,000
- 0 < A_i < 10^4
- A_i は小数部の桁数が 9 以下であるような数として与えられる。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \vdots A_N
出力
積 A_i \cdot A_j が整数であるような添字のペア (i, j) (i < j) の個数を出力せよ。
入力例 1
5 7.5 2.4 17.000000001 17 16.000000000
出力例 1
3
積が整数であるようなペアは以下の 3 個です。
- 7.5 \cdot 2.4 = 18
- 7.5 \cdot 16 = 120
- 17 \cdot 16 = 272
入力例 2
11 0.9 1 1 1.25 2.30000 5 70 0.000000001 9999.999999999 0.999999999 1.000000001
出力例 2
8
Score : 300 points
Problem Statement
You are given N real values A_1, A_2, \ldots, A_N. Compute the number of pairs of indices (i, j) such that i < j and the product A_i \cdot A_j is integer.
Constraints
- 2 \leq N \leq 200\,000
- 0 < A_i < 10^4
- A_i is given with at most 9 digits after the decimal.
Input
Input is given from Standard Input in the following format.
N A_1 A_2 \vdots A_N
Output
Print the number of pairs with integer product A_i \cdot A_j (and i < j).
Sample Input 1
5 7.5 2.4 17.000000001 17 16.000000000
Sample Output 1
3
There are 3 pairs with integer product:
- 7.5 \cdot 2.4 = 18
- 7.5 \cdot 16 = 120
- 17 \cdot 16 = 272
Sample Input 2
11 0.9 1 1 1.25 2.30000 5 70 0.000000001 9999.999999999 0.999999999 1.000000001
Sample Output 2
8