Problem:
 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

Solution (Python):

class BIT2:
    
    def __init__(self, h, w):
        self.w,self.h=w,h
        self.data = [{}for i in range(h+1)]
    
    
    def sum(self, i, j):
        s = 0
        i -= 1
        data = self.data
        while i >= 0:
            el = data[i]
            k = j - 1 
            while k >= 0:
                s += el.get(k, 0)
                k =( k & (k+1)) - 1

            i = (i&(i+1))-1
        return s

    
    def add(self, i, j, x):
        w = self.w; h = self.h
        data = self.data
        while i < h:
            el = data[i]
            k = j
            while k < w:
                el[k] = el.get(k, 0) + x
                k|=(k+1)
            i|=(i+1)
    
    def range_sum(self, x0, x1, y0, y1):
        return self.sum(x1, y1) - self.sum(x1, y0) - self.sum(x0, y1) + self.sum(x0, y0)
ans=0
bit=BIT2(20,20)
for i in range(int(input())):
    a=input().split('.')
    if len(a)==1:
        cnt2,cnt5=9,9
        a=int(a[0])
        while a%2==0 and cnt2<18:
            cnt2+=1
            a//=2
        while a%5==0 and cnt5<18:
            cnt5+=1
            a//=5
    else:
        a=int(a[0])*10**9+int((a[1][::-1].zfill(9))[::-1])
        cnt2,cnt5=0,0
        for j in range(18):
            if a%2==0:
                a//=2
                cnt2+=1
            if a%5==0:
                a//=5
                cnt5+=1
    ans+=bit.range_sum(18-cnt2,19,18-cnt5,19)
    bit.add(cnt2,cnt5,1)
print(ans)

Solution (Python):
from collections import Counter
from decimal import Decimal

def func(n):
    cnt2 = 0
    cnt5 = 0
    while n % 2 == 0:
        n //= 2
        cnt2 += 1
    while n % 5 == 0:
        n //= 5
        cnt5 += 1
    return cnt2, cnt5

def main():
    N = int(input())
    A = [input() for _ in range(N)]
    ctr = Counter()

    for a in A:
        d = Decimal(a)
        d = int(d * 1000000000)
        cnt2, cnt5 = func(d)
        ctr[(cnt2,cnt5)] += 1
    ans = 0
    for (ni1, go1), v1 in ctr.items():
        for (ni2, go2), v2 in ctr.items():
            if not (ni1 + ni2 >= 18 and go1 + go2 >= 18):
                continue
            if ni1 == ni2 and go1 == go2:
                ans += v1 * (v1 - 1)
            else:
                ans += v1 * v2


    print(ans // 2)


if __name__ == "__main__":
    main()

Solution (Python):



n = int(input())
dp = [[0]*19 for _ in range(19)]
dq = [[0]*19 for _ in range(19)]

for i in range(n):
    s = input()
    x = s.find('.')
    if x == -1:
        s = s + '0'*9
    else:
        s = s.replace('.','') + '0'*(10-(len(s)-x))
    s = int(s)
    d2 = 0
    d5 = 0
    for _ in range(18):
        if s%2 != 0:
            break
        s = s//2
        d2 += 1
    for _ in range(18):
        if s%5 != 0:
            break
        s = s//5
        d5 += 1
    dp[d2][d5] += 1
    dq[d2][d5] += 1

for i in range(18,-1,-1):
    for j in range(18,0,-1):
        dp[i][j-1]+=dp[i][j]
for j in range(18,-1,-1):
    for i in range(18,0,-1):
        dp[i-1][j]+=dp[i][j]

ret = 0
for i in range(19):
    for j in range(19):
        if dq[i][j] == 0:
            continue
        ret += dq[i][j] * dp[18-i][18-j]
ret -= dp[9][9]
print(ret//2)

Solution (Python):
import sys
readline = sys.stdin.readline

N = int(readline())

C = [[0] * 19 for i in range(19)]

for i in range(N):
  a = readline().rstrip()
  if "." in a:
    keta = len(a.split(".")[1])
    a = int(a.replace(".","")) * (10 ** (9 - keta))
  else:
    a = int(a) * (10 ** 9)
  cnt2 = 0
  cnt5 = 0
  while a % 2 == 0:
    a //= 2
    cnt2 += 1
  while a % 5 == 0:
    a //= 5
    cnt5 += 1
  C[min(cnt2, 18)][min(cnt5, 18)] += 1




ans = 0

for i in range(9, 19):
  for j in range(9, 19):
    n = C[i][j]
    ans += (n * (n - 1)) // 2


ans_diff = 0
for i in range(19):
  for j in range(19):
    for p in range(19):
      for q in range(19):
        if i == p and j == q:
          continue 
        if i + p < 18 or j + q < 18:
          continue
        ans_diff += C[i][j] * C[p][q]

ans += ans_diff // 2 

print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline

N = int(readline())

C = [[0] * 19 for i in range(19)]

for i in range(N):
  a = readline().rstrip()
  if "." in a:
    keta = len(a.split(".")[1])
    a = int(a.replace(".","")) * (10 ** (9 - keta))
  else:
    a = int(a) * (10 ** 9)
  temp = a
  cnt2 = 0
  cnt5 = 0
  while a % 2 == 0:
    a //= 2
    cnt2 += 1
  while a % 5 == 0:
    a //= 5
    cnt5 += 1
  C[min(cnt2, 18)][min(cnt5, 18)] += 1




ans = 0

for i in range(9, 19):
  for j in range(9, 19):
    n = C[i][j]
    ans += (n * (n - 1)) // 2


ans_diff = 0
for i in range(19):
  for j in range(19):
    for p in range(19):
      for q in range(19):
        if i == p and j == q:
          continue 
        if i + p < 18 or j + q < 18:
          continue
        ans_diff += C[i][j] * C[p][q]

ans += ans_diff // 2 

print(ans)

Solution (Python):
n = int(input())
a = [[0]*37 for _ in range(37)]
b = 0
for _ in range(n):
    A = round(float(input())*10**9)
    for i in range(37):
        if A%2 == 0:
            A //= 2
        else:
            x = i
            break
    for i in range(37):
        if A%5 == 0:
            A //= 5
        else:
            y = i
            break
    a[x][y] += 1
for i in range(37):
    for j in range(37):
        for k in range(i+1, 37):
            for l in range(37):
                if i+k >= 18 and j+l >= 18:
                    b += a[i][j]*a[k][l]
for i in range(37):
    for j in range(37):
        for k in range(j, 37):
            if j == k and i >= 9 and j >= 9:
                b += a[i][j]*(a[i][j]-1)//2
            elif j != k and i >= 9 and j+k >= 18:
                b += a[i][j]*a[i][k]
print(b)

Solution (Python):
"""
小数の状態だと処理しづらいので、与えられた数を全て10**9倍して小数を確実になくした上で
問題文を下記のように言い換える。
「積が10**18の倍数になるような数の組み合わせの数がいくつあるか」
数Aiがあり、Aiの2の素因数の数がn, 5の素因数の数がmのとき、
数Ai自体ですでにmin(n,m)個の0の数を持っている。この場合、のこり必要な0の数はx = 18-min(n,m)個である。
ここで、n == mの場合：
Aiの相方は少なくとも2,5の素因数をそれぞれx個以上持っていなくてはならない。
n > mの場合：
Aiの相方は少なくとも2の素因数をx-(n-m)個、5の素因数をx個持っていなくてはいけない。

m > nの場合：
Aiの相方は少なくとも2の素因数をx個以上、5の素因数をx-(m-n)個以上持っていなくてはならない。
"""
N = int(input())
dp = [[0]*(19) for _ in range(19)]
ans = 0
for _ in range(N):
    a = round(float(input())*pow(10,9))
    two = 0
    while a % 2 == 0 and two < 18:
        a //= 2
        two += 1
    five = 0
    while a % 5 == 0 and five < 18:
        a //= 5
        five += 1

    ans += dp[18-two][18-five]
    for i in range(two+1):
        for j in range(five+1):
            dp[i][j] += 1
print(ans)

Solution (Python):
def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
dp = [[0]*19 for _ in range(19)]


ans = 0
for _ in range(n):
    x = round(float(input()) * pow(10, 9))
    two = div(x, 2)
    five = div(x, 5)
    ans += dp[18 - two][18 - five]
    for i in range(two + 1):
        for j in range(five + 1):
            dp[i][j] += 1

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

n = int(input())
ans = 0
cnt = [[0]*20 for _ in range(45)]
for _ in range(n):
    a = list(map(str, input().rstrip().split(".")))
    x = 0
    if len(a) == 1:
        x = int(a[0]) * 10**9
    else:
        x = int(a[0]) * 10**9 + int(a[1]) * pow(10, 9-len(a[1]))
    cnt_2, cnt_5 = 0, 0
    while x % 2 == 0:
        cnt_2 += 1
        x //= 2
    while x % 5 == 0:
        cnt_5 += 1
        x //= 5
    for i in range(45):
        for j in range(20):
            if cnt_2 + i >= 18 and cnt_5 + j >= 18:
                ans += cnt[i][j]
    cnt[cnt_2][cnt_5] += 1
print(ans)

Solution (Python):
import sys

readline = sys.stdin.readline
class Bit:
    def __init__(self, lst):
        t = 1
        while (t << 1) <= len(lst):
            for i in range(t, len(lst) - t + 1, t << 1):
                lst[i + t - 1] += lst[i - 1]
            t <<= 1
        self.lst = lst

    def add(self, pos, value):
        pos += 1
        while pos <= len(self.lst):
            self.lst[pos - 1] += value
            pos += pos & (-pos)

    def update(self, pos, value):
        diff = value - self.at(pos)
        self.add(pos, diff)

    def at(self, pos):
        return self.sum(pos + 1) - self.sum(pos)
    
    def sum(self, pos):
        
        if pos == 0:
            return 0
        s = 0
        while pos > 0:
            s += self.lst[pos - 1]
            
            pos &= ~(-pos)
        return s
    
def solve():
    N = int(readline())
    A = [float(readline()) for i in range(N)]

    C = [0] * N
    c5s = set()

    for i, a in enumerate(A):
        
        
        b = round(a * (10 ** 9))
        c2, c5 = -9, -9
        while b % 2 == 0:
            b //= 2
            c2 += 1
        while b % 5 == 0:
            b //= 5
            c5 += 1
        
        C[i] = (c2, c5)
    
    Q = [(-a, -b) for a,b in C]

    count0 = sum(a >= 0 and b >= 0 for a,b in C)

    
    s1 = set()
    s2 = set()
    for a,b in C:
        s1.add(a)
        s2.add(b)
    for a,b in Q:
        s1.add(a)
        s2.add(b)
    xs = sorted(s1)
    ys = sorted(s2)
    compA = {v: i for i, v in enumerate(xs)}
    compB = {v: i for i, v in enumerate(ys)}
    C = [(compA[a], compB[b]) for a,b in C]
    Q = [(compA[a], compB[b]) for a,b in Q]
    H, W = len(xs), len(ys)

    C.sort()
    Q.sort(reverse=True)

    bit = Bit([0] * W)
    ans = 0

    j = N - 1
    for x, y in Q:
        while j >= 0 and C[j][0] >= x:
            bit.add(C[j][1], 1)
            j -= 1
        ans += bit.sum(W) - bit.sum(y)

    print((ans - count0) // 2)


solve()

Solution (Python):
import sys
from itertools import chain

readline = sys.stdin.readline
class Bit:
    def __init__(self, lst):
        t = 1
        while (t << 1) <= len(lst):
            for i in range(t, len(lst) - t + 1, t << 1):
                lst[i + t - 1] += lst[i - 1]
            t <<= 1
        self.lst = lst

    def add(self, pos, value):
        pos += 1
        while pos <= len(self.lst):
            self.lst[pos - 1] += value
            pos += pos & (-pos)

    def update(self, pos, value):
        diff = value - self.at(pos)
        self.add(pos, diff)

    def at(self, pos):
        return self.sum(pos + 1) - self.sum(pos)
    
    def sum(self, pos):
        
        if pos == 0:
            return 0
        s = 0
        while pos > 0:
            s += self.lst[pos - 1]
            
            pos &= ~(-pos)
        return s
    
def solve():
    N = int(readline())
    A = [float(readline()) for i in range(N)]

    C = [0] * N
    c5s = set()

    for i, a in enumerate(A):
        
        
        b = round(a * (10 ** 9))
        c2, c5 = -9, -9
        while b % 2 == 0:
            b //= 2
            c2 += 1
        while b % 5 == 0:
            b //= 5
            c5 += 1
        
        C[i] = (c2, c5)
    
    Q = [(-a, -b) for a,b in C]

    count0 = sum(a >= 0 and b >= 0 for a,b in C)

    
    xs = sorted(set(chain((a for a,b in C), (a for a,b in Q))))
    ys = sorted(set(chain((b for a,b in C), (b for a,b in Q))))
    compA = {v: i for i, v in enumerate(xs)}
    compB = {v: i for i, v in enumerate(ys)}
    C = [(compA[a], compB[b]) for a,b in C]
    Q = [(compA[a], compB[b]) for a,b in Q]
    H, W = len(xs), len(ys)

    C.sort()
    Q.sort(reverse=True)

    bit = Bit([0] * W)
    ans = 0

    j = N - 1
    for x, y in Q:
        while j >= 0 and C[j][0] >= x:
            bit.add(C[j][1], 1)
            j -= 1
        ans += bit.sum(W) - bit.sum(y)

    print((ans - count0) // 2)


solve()

Solution (Python):
import sys

readline = sys.stdin.readline
class Bit:
    def __init__(self, lst):
        t = 1
        while (t << 1) <= len(lst):
            for i in range(t, len(lst) - t + 1, t << 1):
                lst[i + t - 1] += lst[i - 1]
            t <<= 1
        self.lst = lst

    def add(self, pos, value):
        pos += 1
        while pos <= len(self.lst):
            self.lst[pos - 1] += value
            pos += pos & (-pos)

    def update(self, pos, value):
        diff = value - self.at(pos)
        self.add(pos, diff)

    def at(self, pos):
        return self.sum(pos + 1) - self.sum(pos)
    
    def sum(self, pos):
        
        if pos == 0:
            return 0
        s = 0
        while pos > 0:
            s += self.lst[pos - 1]
            
            pos &= ~(-pos)
        return s
    
def solve():
    N = int(readline())
    A = [float(readline()) for i in range(N)]

    C = [0] * N
    c5s = set()

    for i, a in enumerate(A):
        b = round(a * (10 ** 9))
        c2, c5 = -9, -9
        while b % 2 == 0:
            b //= 2
            c2 += 1
        
        while b % 5 == 0:
            b //= 5
            c5 += 1
        
        C[i] = (c2, c5)
        c5s.add(c5)
        c5s.add(-c5)

    c5_to_i = {c5: i for i, c5 in enumerate(sorted(c5s))}
    
    C.sort()

    c5_comp = [c5_to_i[c5] for c2, c5 in C]
    
    bit = Bit([0] * len(c5_to_i))

    c5_max = max(c5 for c2, c5 in C)


    ans = 0
    j = N - 1
    for i, (c2, c5) in enumerate(C):
        if c2 < 0:
            l, r = i, N
            while l + 1 < r:
                m = (l + r) // 2
                if C[m][0] + c2 >= 0:
                    r = m
                else:
                    l = m
            if r == N:
                continue
            
            while j >= r:
                bit.add(c5_comp[j], 1)
                j -= 1
            
            ans += bit.sum(c5_to_i[c5_max] + 1) - bit.sum(c5_to_i[-c5])
        else:
            while j < i:
                j += 1
                bit.add(c5_comp[j], -1)
            
            while j > i:
                bit.add(c5_comp[j], 1)
                j -= 1

            ans += bit.sum(c5_to_i[c5_max] + 1) - bit.sum(c5_to_i[-c5])
    
    print(ans)


solve()

Solution (Python):
import numpy as np

N = int(input())

A = []
for i in range(N):
    num = float(input()) * 10 ** 9 + 0.5
    A.append(int(num))


def count2(n):
    ret = 0
    while(n % 2 == 0):
        ret += 1
        n /= 2
    return ret


def count5(n):
    ret = 0
    while(n % 5 == 0):
        ret += 1
        n /= 5
    return ret


table = {}
for i in range(19):
    for j in range(19):
        table[i, j] = 0

for a in A:
    c2 = count2(a)
    c5 = count5(a)
    if(c2 > 18):
        c2 = 18
    if(c5 > 18):
        c5 = 18
    table[c2, c5] += 1

res = 0
for i in range(19):
    for j in range(19):
        for k in range(19):
            for l in range(19):
                if i + k >= 18 and j + l >= 18:
                    if i == k and j == l:
                        res += table[i, j] * (table[i, j] - 1)
                    else:
                        res += table[i, j] * table[k, l]

print(res // 2)

Solution (Python):
import decimal
class Imos_2:
    def __init__(self,W,H):
        self.width=W
        self.height=H
        self.list=[[0]*(W+1) for _ in range(H+1)]

    def Add(self,F,T,C=1):
        Fx,Fy=F
        Tx,Ty=T

        self.list[Fx][Fy]+=C
        self.list[Fx][Ty+1]-=C
        self.list[Tx+1][Fy]-=C
        self.list[Tx+1][Ty+1]+=C

    def Cumulative_Sum(self):
        Y=[[0]*(self.height+1) for _ in range(self.width+1)]

        for x in range(self.width+1):
            S=0
            for y in range(self.height+1):
                S+=self.list[x][y]
                Y[x][y]=S

        for y in range(self.height+1):
            S=0
            for x in range(self.width+1):
                S+=Y[x][y]
                Y[x][y]=S

        return Y

def f(N):
    R=[]
    for k in [2,5]:
        X=N
        Y=0
        while X%k==0:
            X//=k
            Y+=1
        R.append(min(Y,2*Max_power))
    return R

N=int(input())
Max_power=9
A=[0]*N
I=Imos_2(2*Max_power+1,2*Max_power+1)
Power=[0]*N

for i in range(N):
    A[i]=int(decimal.Decimal(input())*(10**Max_power))

for i in range(N):
    (p,q)=f(A[i])
    Power[i]=(p,q)
    I.Add((2*Max_power-p,2*Max_power-q),(2*Max_power,2*Max_power))

J=I.Cumulative_Sum()

Ans=0
for i in range(N):
    p,q=Power[i]
    Y=J[p][q]

    if (p>=Max_power) and (q>=Max_power):
        Y-=1

    Ans+=Y

print(Ans//2)

Solution (Python):
from collections import defaultdict
from math import gcd
nums = defaultdict(int)
for _ in range(int(input())):
  nums[gcd(round(float(input())*(10**9)),10**18)] += 1
nums = tuple(nums.items())
ans = 0
for i, (a,b) in enumerate(nums):
  if a*a%(10**18) == 0:
    ans += b*(b-1)//2
  for (c,d) in nums[i+1:]:
    if a*c%(10**18) == 0:
      ans += b*d
print(ans)

Solution (Python):
from collections import defaultdict

N = int(input())
b = 10**9
A = [int(round(float(input())*b)) for i in range(N)]
dic = defaultdict(int)
for a in A:
    c2, c5 = 0, 0
    while a % 2 == 0 and c2 < 18:
        c2 += 1
        a //= 2
    while a % 5 == 0 and c5 < 18: 
        c5 += 1
        a //= 5
    dic[(c2, c5)] += 1
ans = 0
for i in range(50):
    for j in range(25):
        for k in range(50):
            for l in range(25):
                if i+k >= 18 and j+l >= 18:
                    if i == k and j == l:
                        ans += dic[(i, j)] * (dic[(i, j)] - 1)
                    else:
                        ans += dic[(i, j)] * dic[(k, l)]
print(ans//2)

Solution (Python):
from collections import defaultdict

N = int(input())
b = 10**9
A = [int(round(float(input())*b)) for i in range(N)]
dic = defaultdict(int)
for a in A:
    c2, c5 = 0, 0
    while a % 2 == 0:
        c2 += 1
        a //= 2
    while a % 5 == 0:
        c5 += 1
        a //= 5
    dic[(c2, c5)] += 1
ans = 0
for i in range(50):
    for j in range(25):
        for k in range(50):
            for l in range(25):
                if i+k >= 18 and j+l >= 18:
                    if i == k and j == l:
                        ans += dic[(i, j)] * (dic[(i, j)] - 1)
                    else:
                        ans += dic[(i, j)] * dic[(k, l)]
print(ans//2)

Solution (Python):
from collections import defaultdict

def Com(n, k):
    p, q = 1, 1
    for i in range(n-k+1, n+1):
        p *= i
    for i in range(2, k+1):
        q *= i
    return p//q

N = int(input())
b = 10**9
A = [int(round(float(input())*b)) for i in range(N)]
dic = defaultdict(int)
for a in A:
    c2, c5 = 0, 0
    while a % 2 == 0:
        c2 += 1
        a //= 2
    while a % 5 == 0:
        c5 += 1
        a //= 5
    dic[(c2, c5)] += 1
ans = 0
for i in range(50):
    for j in range(25):
        for k in range(i, 50):
            for l in range(25):
                if not (i==k and j>=l) and i+k >= 18 and j+l >= 18:
                    ans += dic[(i, j)] * dic[(k, l)]
for i in range(50):
    for j in range(25):
        if i+i >= 18 and j+j >= 18 and dic[(i, j)] > 1:
            ans += Com(dic[(i, j)], 2)
print(ans)

Solution (Python):
N = int(input())

def parse(s):
    if '.' not in s:
        return int(s)*10**9
    else:
        n = len(s)-s.find('.')
        s = s[:-n]+s[-n+1:]+(10-n)*'0'
        return  int(s)

A = [parse(input()) for _ in range(N)]
count = []
for i in range(N):
    n2 = 0
    n5 = 0
    n = A[i]
    while True:
        if n%2==0:
            n2 += 1
            n//=2
        else:
            break
    while True:
        if n%5==0:
            n5 += 1
            n//=5
        else:
            break
    n2 = min(n2,18)
    n5 = min(n5,18)
    count.append((n2,n5))

d = {}
for i in range(19):
    for j in range(19):
        d[(i,j)] = 0
for i in range(N):
    d[count[i]] += 1

dsum = {}
for i in range(19):
    for j in range(19):
        dsum[(i,j)] = 0
        for k in range(18-i,19):
            for l in range(18-j,19):
                dsum[(i,j)] += d[(k,l)]

ans = 0
for i in range(N):
    ans += dsum[count[i]]
    if count[i][0]>=9 and count[i][1]>=9:
        ans -= 1
ans //= 2
print(ans)

Solution (Python):
import copy
n = int(input())
def point_shift(s,i):
    p = s.index(".")
    tale = len(s[p+1:])
    if tale <= i:
        return int(s[:p]+s[p+1:].ljust(i,"0"))
    else:
        return int(s[:p]+s[p+1:p+i+1])

a = []
for i in range(n):
    s = input()
    if "." not in s:
        a.append(int(s)*10**9)
    else:
        a.append(point_shift(s,9))

memo = [[0,0] for _ in range(n)]
for i in range(n):
    t = a[i]
    while t%2 == 0:
        t //= 2
        memo[i][0] += 1
    while t%5 == 0:
        t //= 5
        memo[i][1] += 1

l0 = [[0]*100 for _  in range(100)]
for i in range(n):
    l0[memo[i][0]][memo[i][1]] += 1

l1 = copy.deepcopy(l0)
for i in range(100):
    for j in range(98,-1,-1):
        l1[i][j] += l1[i][j+1]
for i in range(98,-1,-1):
    for j in range(100):
        l1[i][j] += l1[i+1][j]


ans = 0
for i in range(100):
    for j in range(100):
        x0,y0 = i,j
        x1,y1 = max(0,18-x0),max(0,18-y0)
        if x0 >= 9 and y0 >= 9:
            ans += l0[x0][y0]*(l1[x1][y1]-1)
        else:
            ans += l0[x0][y0]*l1[x1][y1]
print(ans//2)

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
a = [[0]*19 for i in range(19)]
for i in range(n):
    A = int(float(input())*10**9+0.5)
    m2 = m5 = 0
    while A % 2 == 0:
        A //= 2
        m2 += 1
    while A % 5 == 0:
        A //= 5
        m5 += 1
    m2 = min(m2, 18)
    m5 = min(m5, 18)
    a[m2][m5] += 1

ans = 0
for i in range(19):
    for j in range(19):
        for k in range(19):
            for l in range(19):
                if i + k >= 18 and j + l >= 18:
                    if i == k and j == l:
                        ans += a[i][j] * ( a[k][l] - 1 )
                    else:
                        ans += a[i][j] * a[k][l]
ans //= 2
print(ans)

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def is_ok(arg):
    return a[i][j]+a[arg][j] >= 0

def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

n = INT()
a = [[0]*19 for i in range(19)]
for i in range(n):
    A = int(float(input())*10**9+0.5)
    m2 = m5 = 0
    while A % 2 == 0:
        A //= 2
        m2 += 1
    while A % 5 == 0:
        A //= 5
        m5 += 1
    m2 = min(m2, 18)
    m5 = min(m5, 18)
    a[m2][m5] += 1

ans = 0
for i in range(19):
    for j in range(19):
        for k in range(19):
            for l in range(19):
                if i + k >= 18 and j + l >= 18:
                    if i == k and j == l:
                        ans += a[i][j] * ( a[k][l] - 1 )
                    else:
                        ans += a[i][j] * a[k][l]
ans //= 2
print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N = I()
A = []
dic = DD(int)
for _ in range(N):
  s = S().split(".")
  if len(s) == 1:
    temp = int(s[0])*(10**9)
  else:
    temp = int(s[0])*(10**9)+int(s[1])*(10**(9-len(s[1])))
  _2,_5 = 0,0
  copy = temp
  while copy%2 == 0:
    _2 += 1
    copy //= 2
    if _2 == 18: break
  copy = temp
  while copy%5 == 0:
    _5 += 1
    copy //= 5
    if _5 == 18: break
  dic[(_2,_5)] += 1

ans1 = 0
ans2 = 0
for i2 in range(19):
  for j2 in range(18-i2,19):
    for i5 in range(19):
      for j5 in range(18-i5,19):
        if (i2,i5)==(j2,j5):
          ans1 += dic[(i2,i5)]*(dic[(j2,j5)]-1)
        else:
          ans2 += dic[(i2,i5)]*dic[(j2,j5)]

print((ans1+ans2)//2)

Solution (Python):
n=int(input())
cnt=[[0]*19 for _ in range(19)]
for i in range(n):
  a=input()
  i2,i5=0,0
  if '.' in a:
    b,c=a.split('.')
    i2-=len(c)
    i5-=len(c)
    x=int(b+c)
  else:
    x=int(a)
  while x%2==0:
    x//=2
    i2+=1
  while x%5==0:
    x//=5
    i5+=1
  i2=min(i2,9)
  i5=min(i5,9)
  cnt[i2+9][i5+9]+=1

csum=[[0]*19 for _ in range(19)]

for i in range(17,-1,-1):
  csum[i][-1]=cnt[i][-1]+csum[i+1][-1]
  
for j in range(17,-1,-1):
  csum[-1][j]=cnt[-1][j]+csum[-1][j+1]
  
for i in range(17,-1,-1):
  for j in range(17,-1,-1):
    csum[i][j]=csum[i+1][j]+csum[i][j+1]+cnt[i][j]-csum[i+1][j+1]

ans=0
for i in range(19):
  for j in range(19):
    if cnt[i][j]==0:
      continue
    i2=i-9
    i5=j-9
    x=csum[9-i2][9-i5]
    if 9-i2<=i and 9-i5<=j:
      x-=1
    ans+=x*cnt[i][j]
print(ans//2)

Solution (Python):
N = int(input())
A = []
for i in range(N):
    s = input().strip().split(".")
    a = int(s[0]) * (10 ** 9)
    if len(s) > 1:
        t = s[1] + "0" * (9 - len(s[1]))
        a += int(t)
    A.append(a)
    
c = [[0 for _ in range(19)] for _ in range(19)]

for i in range(N):
    p = A[i]
    cnt2 = 0
    while(not p % 2):
        p /= 2
        cnt2 += 1

    p = A[i]
    cnt5 = 0
    while(not p % 5):
        p /= 5
        cnt5 += 1
    
    c[min(cnt2, 18)][min(cnt5, 18)] += 1
    
ans = 0
for i in range(19):
    for j in range(19):
        for k in range(19):
            for l in range(19):
                if i + k >= 18 and j + l >= 18:
                    if i == k and j == l and c[i][j]:  ans += (c[i][j] * (c[i][j] - 1))
                    else:  ans += (c[i][j] * c[k][l])
print(ans // 2)

Solution (Python):
from decimal import Decimal
N = int(input())

log2 = [0] * (N + 1)
log5 = [0] * (N + 1)
acc = [[0 for i in range(19)] for j in range(19)]
Ans = 0

for i in range(1,N+1):
  
  wk = Decimal(input())
  wk = int(wk * 1000000000)

  
  for cnt in range(1,19):
    if wk % 2 == 0:
      log2[i] += 1
      wk = wk // 2
    else:
      break

  for cnt in range(1,19):
    if wk % 5 == 0:
      log5[i] += 1
      wk = wk // 5
    else:
      break

  acc[log2[i]][log5[i]] += 1
    
for i in range(0,19):
  for j in range(0,19): 
    for k in range(i,19):
      for l in range(0,19):
        if (i + k) >= 18 and (j + l) >= 18 and (i < k or (i == k and j <= l)):
          if acc[i][j] > 0 and acc[k][l] > 0:
            Ans += acc[i][j] * acc[k][l]
            if i >= 9 and j >= 9 and i == k and j == l:
              Ans -= int((acc[i][j] * (acc[i][j] + 1)) / 2)

print(int(Ans))

Solution (Python):
from decimal import Decimal
N = int(input())
A = []
for _ in range(N):
    a = Decimal(input())
    A.append(int(a * 10**9))
C = [[0 for j in range(19)] for i in range(44)]
for a in A:
    i = 0
    k = a
    while k % 2 == 0:
        k //= 2
        i += 1
    j = 0
    k = a
    while k % 5 == 0:
        k //= 5
        j += 1
    C[i][j] += 1
res = 0
for i in range(44):
    for j in range(19):
        for ii in range(44):
            for jj in range(19):
                if i + ii >= 18 and j + jj >= 18:
                    res += C[i][j] * C[ii][jj]
for a in A:
    if a**2 % 10**18 == 0:
        res -= 1
res //= 2
print(res)