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):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter
    n = int(readline())
    c = Counter()
    ans = 0

    for _ in range(n):
        x = input()
        if "." in x:
            p, q = x.split(".")
            l = 9 - len(q)
            y = int(p + q + "0" * l)
        else:
            p = x
            y = int(p + "0" * 9)

        i = 0
        while i < 18:
            if y % (2 ** (i + 1)) != 0:
                break
            i += 1

        j = 0
        while j < 18:
            if y % (5 ** (j + 1)) != 0:
                break
            j += 1

        for k in range(18 - i, 19):
            for l in range(18 - j, 19):
                ans += c[(k, l)]

        c[(i, j)] += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def dev(a):
    d = {}
    for i in (2, 5):
        r = 0
        while a % i == 0:
            r += 1
            a //= i
        d[i] = min(18, r)
    return d


def main():
    N = int(input())
    A = []
    for _ 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(dev(a))
    
    S = [[0] * 19 for _ in range(19)]
    dp = [[0] * 20 for _ in range(20)]
    for a in A:
        S[a[2]][a[5]] += 1

    
    for i in range(19):
        for j in range(19):
            dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j] + S[i][j]
    
    
    res = 0
    for a in A:
        s = 18 - a[2]
        t = 18 - a[5]
        
        r = N - dp[-1][t] - dp[s][-1] + dp[s][t]
        if a[2] >= 9 and a[5] >= 9:
            r -= 1
        
        res += r
    print(res // 2)
    
if __name__ == "__main__":
    main()

Solution (Python):
def main():
    N = int(input())
    cnt = [[0] * 19 for _ in range(44)]
    ans = 0
    for _ in range(N):
        a = input()
        if "." in a:
            b = int(a.replace(".", "")) * 10 ** (10 - (len(a) - a.index(".")))
        else:
            b = int(a) * 10 ** 9
        d2 = 0
        d5 = 0
        while b % 2 == 0:
            d2 += 1
            b //= 2
        while b % 5 == 0:
            d5 += 1
            b //= 5
        for i in range(max(0, 18-d2), 44):
            for j in range(max(0, 18-d5), 19):
                ans += cnt[i][j]
        cnt[d2][d5] += 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def howmany2_5(x):
    x = round(x * 10 ** 9)
    n2, n5 = 0, 0
    while x % 2 == 0:
        n2 += 1
        x //= 2
    while x % 5 == 0:
        n5 += 1
        x //= 5
    
    if n2 > 18:
        n2 = 18
    if n5 > 18:
        n5 = 18
    
    return (n2, n5)

def lower_bound_0(A, x):
    s, t = -1, len(A)
    while t - s > 1:
        m = (s + t) // 2
        if A[m][0] >= x:
            t = m
        else:
            s = m
    
    return t
    

def upper_bound_0(A, x):
    s, t = -1, len(A)
    while t - s > 1:
        m = (s + t) // 2
        if A[m][0] > x:
            t = m
        else:
            s = m
    
    return t
    
def lower_bound_1(A, x):
    s, t = -1, len(A)
    while t - s > 1:
        m = (s + t) // 2
        if A[m] >= x:
            t = m
        else:
            s = m
            
    return t

def upper_bound_1(A, x):
    s, t = -1, len(A)
    while t - s > 1:
        m = (s + t) // 2
        if A[m] > x:
            t = m
        else:
            s = m
            
    return t


N = int(input())
A = [howmany2_5(float(input())) for _ in range(N)]
A.sort()
B = []
for i in range(19):
    B.append(list(map(lambda x: x[1], A[lower_bound_0(A, i): upper_bound_0(A, i)])))
C = []
for i in range(19):
    C.append([upper_bound_1(B[i], j) - lower_bound_1(B[i], j) for j in range(19)])
    
ans = 0
for i in range(9):
    for j in range(19):
        cnt = C[i][j]
        for k in range(18 - i, 19):
            ans += sum(C[k][18-j:]) * cnt
    

for i in range(9, 19):
    for j in range(9):
        cnt = C[i][j]
        for k in range(9, 19):
            ans += sum(C[k][18-j:]) * cnt

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

print(ans)

Solution (Python):
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

class BIT:
    '''
    0-indexed
    '''
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.depth = N.bit_length()

    def _bitsum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i ^= i & -i
        return ret

    def bitsum(self, l, r=None): 
        if r is None:
            return self._bitsum(l)
        else:
            return self._bitsum(r) - self._bitsum(l)

    def bitadd(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        return

    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        v = 1 << self.depth
        for i in range(self.depth, -1, -1):
            k = pos + v
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += v
            v >>= 1
        return pos + 1, sum_


def solve():
    n = ni()
    g = [BIT(20) for _ in range(19)]
    ans = 0
    for _ in range(n):
        a = input().split('.')
        x = int(a[0])*10**9
        if len(a) > 1:
            x += int(a[1] + '0' * (9-len(a[1])))
        t = 0; f = 0
        while x % 2 == 0:
            t += 1
            x //= 2
        while x % 5 == 0:
            f += 1
            x //= 5
        if t > 18: t = 18
        if f > 18: f = 18
        for i in range(18-f, 19):
            ans += g[i].bitsum(18-t, 19)
        g[f].bitadd(t, 1)
    print(ans)
    return

solve()

Solution (Python):
from math import gcd
from collections import Counter

N = int(input())
C = Counter()
for i in range(N):
    x = round(float(input()) * 10 ** 9)
    C[gcd(x, 10**18)] += 1

ans = 0
for k1, v1 in C.items():
    for k2, v2 in C.items():
        if k1 * k2 % 10 ** 18 == 0:
            if k1 == k2:
                ans += v1 * (v1 - 1) // 2
            if k1 < k2:
                ans += v1 * v2

print(ans)

Solution (Python):
n = int(input())
cnt = [[0] * 19 for i in range(19)]
ans = 0
for i in range(n):
	a = int(float(input()) * 10**9 + 0.5)
	c2, c5 = -9, -9
	while a % 2 == 0:
		c2 += 1
		a //= 2
	while a % 5 == 0:
		c5 += 1
		a //= 5
	cnt[min(c2, 9)][min(c5, 9)] += 1
	if c2 >= 0 and c5 >= 0:
		ans -= 1
for i in range(-9, 10):
	for j in range(-9, 10):
		for x in range(-i, 10):
			for y in range(-j, 10):
				ans += cnt[i][j] * cnt[x][y]
print(ans // 2)

Solution (Python):
def decomp(m):
    p2=0
    p5=0
    while m%2==0:
        m//=2
        p2+=1
        if p2>18:
            break
    while m%5==0:
        m//=5
        p5+=1
        if p5>18:
            break
    return p2,p5

n=int(input())
table=[[0]*20 for _ in range(20)]
ans=0
for i in range(n):
    a=float(input())
    ax=int(round(a*10**9))
    p2,p5=decomp(ax)
    if i!=0:
        for j in range(max(0,18-p2),20):
            ans+=sum(table[j][max(18-p5, 0):])
    table[p2][p5]+=1

print(ans)

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

n = int(input())
As = [int(round(float(input())*10**9)) for _ in  range(n)]

fives = [0] * n
twos = [0] * n
cnts = [[0] * 20 for i in range(20)]
for i, a in enumerate(As):
    tmp = a
    five = 0
    two = 0
    while tmp % 5 == 0:
        five += 1
        tmp //= 5
    while tmp % 2 == 0:
        two += 1
        tmp //= 2
    cnts[min(two,18)][min(five,18)] += 1



ans = 0
for i1 in range(19):
    for j1 in range(19):
        for i2 in range(19):
            for j2 in range(19):
                if i1+i2 >= 18 and j1+j2>=18:
                    ans += cnts[i1][j1]*cnts[i2][j2]


for i in range(19):
    for j in range(19):
        if i*2 >= 18 and j*2 >= 18:
            ans -= cnts[i][j]


ans //= 2
print(ans)

Solution (Python):
n = int(input())
As = [int(round(float(input())*10**9)) for _ in  range(n)]

fives = [0] * n
twos = [0] * n
cnts = [[0] * 20 for i in range(20)]
for i, a in enumerate(As):
    tmp = a
    five = 0
    two = 0
    while tmp % 5 == 0:
        five += 1
        tmp //= 5
    while tmp % 2 == 0:
        two += 1
        tmp //= 2
    cnts[min(two,18)][min(five,18)] += 1



ans = 0
for i1 in range(19):
    for j1 in range(19):
        for i2 in range(19):
            for j2 in range(19):
                if i1+i2 >= 18 and j1+j2>=18:
                    ans += cnts[i1][j1]*cnts[i2][j2]


for i in range(19):
    for j in range(19):
        if i*2 >= 18 and j*2 >= 18:
            ans -= cnts[i][j]


ans //= 2
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
def waru(N,num):
  cnt = 0
  while N%num==0:
    N //= num
    cnt += 1
  return cnt
def solve():
  N = int(input())
  num = [[0]*101 for _ in range(101)]
  lis = [0]*N
  for i in range(N):
    a = int(round(float(input())*10**9))
    p,q = waru(a,2)-9-50,waru(a,5)-9-50
    num[p][q] += 1
    lis[i] = [p,q]
  cum2 = [[0]*101 for _ in range(101)]
  for i in range(99,-1,-1):
    for j in range(99,-1,-1):
      cum2[i][j] = cum2[i+1][j]+cum2[i][j+1]-cum2[i+1][j+1]+num[i][j]
  ans = 0
  for i in range(N):
    p,q = lis[i]
    x,y = p+50,q+50
    p = -x-50
    q = -y-50
    ans += cum2[p][q]
    if x>=0 and y>=0:
      ans -= 1
  return ans//2
print(solve())

Solution (Python):
from decimal import Decimal
def waru(N,num):
  cnt = 0
  while N%num==0:
    N //= num
    cnt += 1
  return cnt
def solve():
  N = int(input())
  num = [[0]*101 for _ in range(101)]
  lis = [0]*N
  for i in range(N):
    a = int(round(float(input())*10**9))
    p,q = waru(a,2)-9-50,waru(a,5)-9-50
    num[p][q] += 1
    lis[i] = [p,q]
  cum2 = [[0]*101 for _ in range(101)]
  for i in range(99,-1,-1):
    for j in range(99,-1,-1):
      cum2[i][j] = cum2[i+1][j]+cum2[i][j+1]-cum2[i+1][j+1]+num[i][j]
  ans = 0
  for i in range(N):
    p,q = lis[i]
    x,y = p+50,q+50
    p = -x-50
    q = -y-50
    ans += cum2[p][q]
    if x>=0 and y>=0:
      ans -= 1
  return ans//2
print(solve())

Solution (Python):
from decimal import Decimal
def waru(N,num):
  cnt = 0
  while N%num==0:
    N //= num
    cnt += 1
  return cnt
def solve():
  N = int(input())
  num = [[0]*101 for _ in range(101)]
  lis = [0]*N
  for i in range(N):
    a = int(round(float(input())*10**9))
    p,q = waru(a,2)-9-50,waru(a,5)-9-50
    num[p][q] += 1
    lis[i] = [p,q]
  cum2 = [[0]*101 for _ in range(101)]
  for i in range(99,-1,-1):
    for j in range(99,-1,-1):
      cum2[i][j] = cum2[i+1][j]+cum2[i][j+1]-cum2[i+1][j+1]+num[i][j]
  ans = 0
  for i in range(N):
    p,q = lis[i]
    x,y = p+50,q+50
    p = -x-50
    q = -y-50
    ans += cum2[p][q]
    if x>=0 and y>=0:
      ans -= 1
  return ans//2
print(solve())

Solution (Python):
N = int(input())
A = [input() for _ in range(N)]

D = [[0 for j in range(40)] for i in range(60)]

for a in A:
    
    B=0;k=0
    for j in range(len(a)):
        if a[j]!='.':
            B=B*10
            B=B+int(a[j])
        if a[j]=='.':
            k=len(a)-j-1
    
    
    t=0;f=0
    b=B
    while b%2==0:
        t+=1
        b=b//2
    b=B
    while b%5==0:
        f+=1
        b=b//5
    
    
    
    
    D[t-k+10][f-k+10]+=1
    

Ans=0
for i in range(len(D)):
    for j in range(len(D[i])):
        for k in range(len(D)):
            for l in range(len(D[k])):
                
                if i+k-20>=0 and j+l-20>=0 and not(i==k and j==l):
                    Ans = Ans+D[i][j]*D[k][l]


Ans = Ans//2



for i in range(len(D)):
    for j in range(len(D[i])):
        if i-10>=0 and j-10>=0:
            Ans = Ans + D[i][j]*(D[i][j]-1)//2

print(Ans)

Solution (Python):
from math import gcd
from collections import Counter
import sys

N = int(input())
K = 10**9
L = 10**18
A = [0] * N
C = Counter()
ans = 0

for i in range(N):
	A[i] = round(K * float(input()))
	C[gcd(A[i],L)] += 1 
	
for k1,v1 in C.items():
	for k2 ,v2 in C.items():
		if k1 == k2:
			if k1*k2 % L == 0:
				ans += v1*(v1-1)/2
		elif k1 < k2:
			if k1*k2 % L == 0:
				ans += v1 * v2

print(int(ans))

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

n = int(input())
ans = 0
c = []
for i in range(n):
	x = input()[:-1]
	if '.' not in x:
		x += '.'
	cnt = len(x) - x.rfind('.') - 1
	x = int(x.replace('.', '')) * 10 ** (9 - cnt)
	
	a = b = 0
	while not x & 1:
		a += 1
		x >>= 1
	while not x % 5:
		b += 1
		x //= 5
	c.append((a, b))
c.sort()

s = [0] * 20
j = n - 1
for i in range(n):
	while j >= 0 and c[j][0] >= 18 - c[i][0]:
		s[c[j][1]] += 1
		j -= 1
	
	for k in range(18 - c[i][1], 20):
		ans += s[k]
for i in c:
	if 2 * min(i) >= 18:
		ans -= 1
print(ans // 2)

Solution (Python):


from decimal import *

n = int(input())
a_l = [int(Decimal(input()) * 10**9) for x in range(n)]

list = [[0] * 19 for _ in range(19)]
cs_list = [[0] * 19 for _ in range(19)]
b_l = [0, 0] * n

for i in range(n):
    _t2 = 0
    _t5 = 0
    _a = a_l[i]
    while _a % 2 == 0 and _t2 < 18:
        _t2 += 1
        _a /= 2

    _a = a_l[i]
    while _a % 5 == 0 and _t5 < 18:
        _t5 += 1
        _a /= 5
    
    list[_t2][_t5] += 1
    b_l[i] = [_t2, _t5]

for i in range(19):
    for j in range(19):
        for k in range(i+1):
            for l in range(j+1):
                cs_list[k][l] += list[i][j]

ans = 0
for i in range(n):
    _t,_f = b_l[i]
    if _t >= 9 and _f >= 9:
        ans -= 1
    ans += cs_list[18-_t][18-_f]
        
print(ans // 2)

Solution (Python):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
d = dd(int)
a = []
for i in range(N):
  t = input()[: -1]
  x, y = "", ""
  z = 0
  if "." in t:
    x, y = t.split(".")
    y = y.ljust(9, "0")
    z = int(x) * 10 ** 9 + int(y)
  else: z = int(t) * 10 ** 9
  zz = 1
  while z % 2 == 0:
    z //= 2
    zz *= 2
  while z % 5 == 0:
    z //= 5
    zz *= 5
  d[zz] += 1
  a.append(zz)
ks = sorted(d.keys())
table = dd(int)
for k in ks:
  for kk in ks:
    z = k * kk
    c = 0
    while z % 10 == 0:
      z //= 10
      c += 1
    table[k * kk] = c >= 18
res = 0
for x in ks:
  cc = N
  for k in ks:
    z = x * k
    if table[z]:
      cc -= x == k
      continue
    cc -= d[k]
  res += cc * d[x]
print(res // 2)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7
MAX = 50


def resolve():
    n = int(input())

    D = [[0] * MAX for _ in range(MAX)]
    for _ in range(n):
        a = int(round(float(input()) * 10 ** 9))
        t = a
        x = 0
        while t % 2 == 0:
            t //= 2
            x += 1
        t = a
        y = 0
        while t % 5 == 0:
            t //= 5
            y += 1
        D[x][y] += 1

    res = 0
    for x1 in range(MAX):
        for y1 in range(MAX):
            for x2 in range(max(0, 18 - x1), MAX):
                for y2 in range(max(0, 18 - y1), MAX):
                    if x1 == x2 and y1 == y2:
                        res += D[x1][y1] * (D[x1][y1] - 1)
                    else:
                        res += D[x1][y1] * D[x2][y2]
    print(res // 2)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
from collections import defaultdict
from math import gcd

def input(): return sys.stdin.readline()

K = 1_000_000_000
L = K**2
D = defaultdict(int)
for _ in range(int(input())):
    D[gcd(round(float(input()) * K), L)] += 1

D = tuple(D.items())
ans = 0
for i, (k1, v1) in enumerate(D):
    if k1*k1 % L == 0:
        ans += v1*(v1-1) // 2
    for k2, v2 in D[i+1:]:
        if k1*k2 % L == 0:
            ans += v1 * v2
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
enum = enumerate
inf = 1001001002002002002

import random

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().rstrip().split()))

def vinput(rep=1, ty=int, cvt=list):
	return cvt(ty(input().rstrip()) for _ in "*"*rep)

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

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

def bye(res):
	sT = "No Yes".split()
	print(sT[res])
	

def sol(N,vF):
	P,E = 1e9, 1e-3
	vA = [int(f*P+E) for f in vF]
	
	def divcnt(n):
		m,n = n,n
		a,b = 0,0
		while m%2<1: m//=2; a+=1
		while n%5<1: n//=5; b+=1
		return a,b

	vM = [divcnt(a) for a in vA]
	
	mX = [[0,]*50 for _ in "*"*50]
	for a,b in vM:
		mX[b][a] += 1
	
	mC = [[0,]*51,]
	for vX in mX:
		vC = [0,]
		t = 0
		for c,x in zip(mC[-1][1:],vX):
			t += x
			vC.append(t+c)
		mC.append(vC)
	
	
	
	res = 0
	
	for a,b in vM:
		x = max(18-a, 0)
		y = max(18-b, 0)
		t = N - mC[y][-1] - mC[-1][x] + mC[y][x]
		if t and x<=a and y<=b:
			t-=1
		
		
		res += t

	print(res//2)


def main():
	N, = linput()
	sol(N, vinput(N,float))

if __name__ == "__main__":
	main()

Solution (Python):
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=[input() for i in range(n)]
lst=[0]*n

def chenge(m):
    nn,mm=m.split(".")
    mm+=(9-len(mm))*"0"
    return int(nn+mm)

for i in range(n):
    if "." in a[i]:
        lst[i]=chenge(a[i])
    else:
        lst[i]=int(a[i]+9*"0")



tf=[0]*n
for i in range(n):
    mm=lst[i]
    t,f=0,0
    while mm%2==0:
        t+=1
        mm//=2
    while mm%5==0:
        f+=1
        mm//=5
    tf[i]=(t,f)


rui=[[0]*50 for i in range(50)]
for i in range(n):
    t,f=tf[i]
    rui[t][f]+=1

for i in range(49):
    for j in range(49):
        rui[48-i][48-j]+=rui[49-i][48-j]+rui[48-i][49-j]-rui[49-i][49-j]


ans=0
for i in range(n):
    t,f=tf[i]
    ans+=rui[max(0,18-t)][max(0,18-f)]
    if t>=9 and f>=9:
        ans-=1
    
print(ans//2)

Solution (Python):
import sys
from collections import defaultdict
from math import gcd

def input(): return sys.stdin.readline().strip()

K = 10**9
L = 10**18
D = defaultdict(int)
for _ in range(int(input())):
    D[gcd(round(float(input()) * K), L)] += 1

D = tuple(D.items())
ans = 0
for i, (k1, v1) in enumerate(D):
    if k1*k1 % L == 0:
        ans += v1*(v1-1) // 2
    for k2, v2 in D[i+1:]:
        if k1*k2 % L == 0:
            ans += v1 * v2
print(ans)

Solution (Python):
import sys
from collections import defaultdict
from math import gcd

def input(): return sys.stdin.readline().strip()

K = 10**9
L = 10**18
D = defaultdict(int)
for _ in range(int(input())):
    D[gcd(round(float(input()) * K), L)] += 1

D = tuple(D.items())
ans = 0
for i, (k1, v1) in enumerate(D):
    if k1*k1 % L == 0:
        ans += v1*(v1-1) // 2
    for k2, v2 in D[i+1:]:
        if k1*k2 % L == 0:
            ans += v1 * v2
print(ans)

Solution (Python):
from collections import defaultdict

def conv(s):
    if "." not in s:
        s += '.'
    s = s.rstrip('0')
    t = len(s) - s.find('.') - 1
    a = int(s.replace('.', ''))
    if a == 0:
        return (0, 0)
    x, y = -t, -t
    while a % 5 == 0:
        x += 1
        a //= 5
    y += len(bin(a&-a))-3
    return (x, y)

_, *A = open(0).read().split()

d = defaultdict(int)
for a in A:
    d[conv(a)] += 1

result = 0
d = list(d.items())
for i, ((x, y), cnt) in enumerate(d):
    if x >= 0 and y >= 0:
        result += cnt * (cnt - 1) // 2
    for (m, n), cnt2 in d[i+1:]:
        if x + m >= 0 and y + n >= 0:
            result += cnt * cnt2
print(result)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
lst = []
for _ in range(n):
    a = input().split(".")
    if len(a) == 1:
        a[0] = a[0] + '0' * 9
        lst.append(int(a[0]))
    else:
        l = len(a[1])
        tmp = a[0] + a[1] + '0' * (9 - l)
        lst.append(int(tmp))


two = []
five = []
for i in lst:
    j = i
    cnt = 0
    while j % 2 == 0:
        j //= 2
        cnt += 1
    two.append(cnt)
    j = i
    cnt = 0
    while j % 5 == 0:
        j //= 5
        cnt += 1
    five.append(cnt)

a = [[0] * 100 for _ in range(100)]
for i, j in zip(two, five):
    a[i][j] += 1

S = [[0] * 100 for _ in range(100)]
for i in range(1, 100):
    for j in range(1, 100):
        S[i][j] = a[i-1][j-1] + S[i][j - 1] + S[i - 1][j] - S[i - 1][j - 1]

ans = 0
for i, j in zip(two, five):
    if 18 - i < 0:
        i = 18
    if 18 - j < 0:
        j = 18
    ans += S[-1][-1] - S[-1][18 - j] - S[18 - i][-1] + S[18 - i][18 - j]
    if i + i >= 18 and j + j >= 18:
        ans -= 1
print(ans // 2)

Solution (Python):
MOD=10**9
from decimal import Decimal
import sys
input=sys.stdin.readline
    
def w(i,m):
    cnt=0
    while(i>0 and i%m==0):
        i//=m
        cnt+=1
    return cnt

N=int(input())
A=[int(Decimal(input())*Decimal(MOD)) for i in range(N)]
dic=[{} for i in range(N)]
dp=[[0]*51 for i in range(51)]

for i in range(N):
    dic[i][2],dic[i][5]=w(A[i],2),w(A[i],5)
    dp[dic[i][2]][dic[i][5]]+=1

for i in reversed(range(51)):
    for j in reversed(range(51)):
        if i==50 and j==50:
            continue
        if i==50:
            dp[i][j]+=dp[i][j+1]
        elif j==50:
            dp[i][j]+=dp[i+1][j]
        else:
            dp[i][j]+=dp[i][j+1]+dp[i+1][j]-dp[i+1][j+1]
ans=0

for i in range(N):
    t,f=max(18-dic[i][2],0),max(18-dic[i][5],0)
    res=dp[t][f]
    if t<=dic[i][2] and f<=dic[i][5]:
        res-=1
    ans+=res
print(ans//2)

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
num=[[0]*23 for _ in range(40)]
for i in range(n):
	s=int(float(input())*(10**9)+0.5)
	two=-9;five=-9
	while s%2==0:
		s//=2
		two+=1
	while s%5==0:
		s//=5
		five+=1
	num[two+9][five+9]+=1
ans=0
for i in range(40):
	for j in range(23):
		for k in range(18-i,40):
			for l in range(18-j,23):
				if (i,j)==(k,l):
					ans+=num[i][j]*(num[i][j]-1)
				else:
					ans+=num[i][j]*num[k][l]
print(ans//2)

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

    
def w(i,m):
    cnt=0
    while(i>0 and i%m==0):
        i//=m
        cnt+=1
    return cnt

N=int(input())
A=[int(Decimal(input())*Decimal(1000000000)) for i in range(N)]
dic=[None for i in range(N)]
dp=[[0]*51 for i in range(51)]

for i in range(N):
    d={}
    d[2],d[5]=w(A[i],2),w(A[i],5)
    dp[d[2]][d[5]]+=1
    dic[i]=d

for i in reversed(range(51)):
    for j in reversed(range(51)):
        if i==50 and j==50:
            continue
        if i==50:
            dp[i][j]+=dp[i][j+1]
        elif j==50:
            dp[i][j]+=dp[i+1][j]
        else:
            dp[i][j]+=dp[i][j+1]+dp[i+1][j]-dp[i+1][j+1]
ans=0

for i in range(N):
    d=dic[i]
    a,b=d[2],d[5]
    t,f=max(18-a,0),max(18-b,0)
    res=dp[t][f]
    if t<=a and f<=b:
        res-=1
    ans+=res
print(ans//2)

Solution (Python):
def decomp(m):
    p2=0
    p5=0
    while m%2==0:
        m//=2
        p2+=1
    while m%5==0:
        m//=5
        p5+=1
    return p2,p5

n=int(input())
table=[[0]*50 for _ in range(50)]
ans=0
for i in range(n):
    a=input().split('.')
    if len(a)==1:
        ax=int(a[0]+'0'*9)
    else:
        ax=int(a[0]+a[1]+'0'*(9-len(a[1])))
    p2,p5=decomp(ax)
    if i!=0:
        for j in range(18-p2,50):
            ans+=sum(table[j][18-p5:])
    table[p2][p5]+=1

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
 
 
def divide(n):
    c1, c2 = 0, 0
    while (n%2 == 0):
        c1 += 1
        n //= 2
    while (n%5 == 0):
        c2 += 1
        n //= 5
    return (c1, c2)
    
 
def main():
    n = int(input())
    a = [None]*n
    for i in range(n):
        sub = input().replace("\n", "")
        if "." in sub:
            x, y = map(str, sub.split("."))
            s = int(x)*1000000000+10**(9-len(y))*int(y)
        else:
            s = int(sub)
            s *= 1000000000
        a[i] = divide(s)
 
    dp = [[0]*100 for _ in range(100)]
    for i in range(n):
        c1, c2 = a[i]
        dp[c1][c2] += 1
    
    for i in range(98, -1, -1):
        for j in range(98, -1, -1):
            dp[i][j] += dp[i+1][j]+dp[i][j+1]-dp[i+1][j+1]
 
    ans = 0
    for i in range(n):
        c1, c2 = a[i]
        if (c1 >= 9 and c2 >= 9):
            ans -= 1
        if c1 >= 18 and c2 >= 18:
            ans += dp[0][0]
            continue
        if c1 >= 18:
            ans += dp[0][18-c2]
            continue
        if c2 >= 18:
            ans += dp[18-c1][0]
            continue
        ans += dp[18-c1][18-c2]
        
    print(ans//2)
    
    
    
if __name__ == "__main__":
    main()

Solution (Python):
from decimal import *
N = int(input())
A = []
for _ in range(N):
  A.append(int(Decimal(input()) * 10**9))

KMAX = 20

X = [[0 for _ in range(KMAX)] for _ in range(KMAX)]

for a in A:
  i,j = 0,0
  wk = a
  for i in range(KMAX):
    if a%2 == 0:
      a = a // 2
    else:
      break
  for j in range(KMAX):
    if a%5 == 0:
      a = a // 5
    else:
      break
  
  X[i][j] += 1
  


 
  
cnt = 0
for i in range(KMAX):
  for j in range(KMAX):
    for k in range(KMAX):
      for l in range(KMAX):
        if i+k < 18 or j+l < 18:
          continue
        if X[i][j] * X[k][l] == 0:
          continue
        
        if i==k and j==l:
          cnt += X[i][j] * (X[i][j] - 1)
        else:
          cnt += X[i][j] * X[k][l]
print(cnt//2)

Solution (Python):


N = int(input())
A = [input() for _ in range(N)]

def count(a):
  if '.' in a:
    c = a.split('.')
    n = int(c[0]+c[1])
    count2 = count5 = 9 - len(c[1])
  else:
    n = int(a)
    count2 = count5 = 9
  while n%2==0 and count2<18:
    n //= 2
    count2 += 1
  while n%5==0 and count5<18:
    n //= 5
    count5 += 1
  return count2, count5

Z = [[0 for _ in range(19)] for _ in range(19)]
answer = 0
for a in A:
  c2, c5 = count(a)
  answer += Z[18-c2][18-c5]
  for i in range(c2+1):
    for j in range(c5+1):
      Z[i][j] += 1

print(answer)

Solution (Python):

import numpy as np
from decimal import Decimal

N = int(input())
A = [int(10**9*Decimal(input())) for _ in range(N)]

def count(a):
  n = a
  count2 = count5 = 0
  while n%2 == 0 and count2<18:
    n //= 2
    count2 += 1
  while n%5 == 0 and count5<18:
    n //= 5
    count5 += 1
  return count2,count5

Z = np.zeros((19,19), dtype=np.int64)
answer = 0
for a in A:
  c2,c5 = count(a)
  answer += Z[18-c2,18-c5]
  Z[:c2+1,:c5+1] += 1

print(answer)

Solution (Python):

import numpy as np

N = int(input())
A = [input() for _ in range(N)]

def count(a):
  if '.' in a:
    c = a.split('.')
    n = int(c[0]+c[1])
    count2 = count5 = 9 - len(c[1])
  else:
    n = int(a)
    count2 = count5 = 9
  while n%2 == 0 and count2<18:
    n //= 2
    count2 += 1
  while n%5 == 0 and count5<18:
    n //= 5
    count5 += 1
  return count2,count5

Z = np.zeros((19,19), dtype=np.int64)
answer = 0
for a in A:
  c2,c5 = count(a)
  answer += Z[18-c2,18-c5]
  Z[:c2+1,:c5+1] += 1

print(answer)

Solution (Python):

import numpy as np

N = int(input())
A = [input() for _ in range(N)]

def count(a):
  if '.' in a:
    c = a.split('.')
    n = int(c[0]+c[1])
    count2 = 9 - len(c[1])
    count5 = 9 - len(c[1])
  else:
    n = int(a)
    count2 = 9
    count5 = 9
  while n%2 == 0 and count2<18:
    n //= 2
    count2 += 1
  while n%5 == 0 and count5<18:
    n //= 5
    count5 += 1
  return count2,count5

Z = np.zeros((19,19), dtype=np.int64)
answer = 0
for a in A:
  c2,c5 = count(a)
  answer += Z[18-c2,18-c5]
  Z[:c2+1,:c5+1] += 1

print(answer)

Solution (Python):

import numpy as np

N = int(input())
A = [input() for _ in range(N)]

def count(a):
  if '.' in a:
    c = a.split('.')
    n = int(c[0]+c[1])
    count2 = 9 - len(c[1])
    count5 = 9 - len(c[1])
  else:
    n = int(a)
    count2 = 9
    count5 = 9
  while n%2 == 0 and count2<18:
    n //= 2
    count2 += 1
  while n%5 == 0 and count5<18:
    n //= 5
    count5 += 1
  return count2,count5

Z = np.zeros((19,19), dtype=np.int64)
answer = 0
for a in A:
  c2,c5 = count(a)
  if max(c2,c5)>18 or min(c2,c5)<0:
    print(a,c2,c5)
  answer += Z[18-c2,18-c5]
  Z[:c2+1,:c5+1] += 1

print(answer)

Solution (Python):
import sys
from collections import Counter
from math import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 19 + 7
EPS = 10 ** -10

N = INT()
K = 10**9
L = 10**18
A = [0] * N
C = Counter()
for i in range(N):
    a = float(input())
    
    A[i] = round(a * K)
    C[gcd(A[i], L)] += 1

ans = 0
for k1, v1 in C.items():
    for k2, v2 in C.items():
        if k1 == k2:
            if k1*k2 % L == 0:
                ans += v1*(v1-1) // 2
        elif k1 < k2:
            if k1*k2 % L == 0:
                ans += v1 * v2
print(ans)