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

import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def a(s):
	if s.count('.')==0:
		n2=0
		n5=0
		v = int(s)
	else:
		p = s.index('.')
		n2 = -(len(s) - p - 1)
		n5 = -(len(s) - p - 1)
		if p == 1 and s[0]=='0':
			v= int(s[2:])
		else:
			v = int(s[:p]+s[p+1:])
	while v % 2 == 0:
		v = v//2
		n2+=1
	while v % 5 == 0:
		v = v//5
		n5+=1
	return str(n2)+'_'+str(n5)

def main():
	n = int(input())
	
	al = [a(input()) for _ in range(n)]
	cal = collections.Counter(al)
	
	ret = 0
	pp = set()
	for k in cal:
		for k2 in cal:
			if k+'_'+k2 in pp:
				continue
			
			if k==k2:
				a2, a5 = map(int, k.split('_'))
				if a2>=0 and a5 >= 0:
					ret += cal[k]*(cal[k]-1)//2
			else:
				a2, a5 = map(int, k.split('_'))
				b2, b5 = map(int, k2.split('_'))
				if a2+b2 >= 0 and a5+b5 >= 0:
					ret += cal[k]*cal[k2]
				
			pp.add(k+'_'+k2)
			pp.add(k2+'_'+k)
			
			
	return ret
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7


def ddprint(x):
  if DBG:
    print(x)

OFS=20
KK = 41
n = inn()
d = [[0]*KK for i in range(KK)]
for i in range(n):
    a = ins()
    p = a.find('.')
    if p<0:
        v = int(a)
        k = 0
    else:
        b = a[:p]+a[p+1:]
        v = int(b)
        k = len(a)-1-p
    x2 = 0
    while v%2==0:
        x2 += 1
        v //= 2
    x2 = min(x2,OFS)
    x5 = 0
    while v%5==0:
        x5 += 1
        v //= 5
    x5 = min(x5,OFS)
    d[x2-k+OFS][x5-k+OFS] += 1







ans = 0
h = {}
for p in range(KK):
    for q in range(KK):
        sm = 0 if p<OFS or q<OFS else (d[p][q]*(d[p][q]-1)//2)
        
        
        for r in range(-p+2*OFS,KK):
            
            
            for s in range(-q+2*OFS,KK):
                if (r,s)==(p,q) or (r,s,p,q) in h:
                    continue
                h[(p,q,r,s)] = 1
                sm += d[p][q]*d[r][s]
                
                
        ans += sm
print(ans)

Solution (Python):
n=int(input())
G=[[0]*20 for i in range(45)]
A=[0,0,0,0]
for i in range(n):
  S=list(input())
  s=""
  f=0
  a=0
  for j in S:
    if j==".":
      f=1
    else:
      s=s+j
      if f==1:
        a=a+1
  A[0]=int(s)
  A[1]=a
  m=int(s)
  c=0
  while m%10==0:
    c=c+1
    m=m//10
  A[0]=m
  A[1]-=c
  m=A[0]
  c=0
  while m%2==0:
    c=c+1
    m=m//2
  A[2]=c
  c=0
  m=A[0]
  while m%5==0:
    c=c+1
    m=m//5
  A[3]=c
  G[A[2]-A[1]+9][A[3]-A[1]+9]+=1
B=[[0]*21 for i in range(46)]
for i in range(44,-1,-1):
  for j in range(19,-1,-1):
    B[i][j]=B[i+1][j]+B[i][j+1]-B[i+1][j+1]+G[i][j]
ans=0
for i in range(45):
  for j in range(20):
    ans=ans+G[i][j]*B[max(0,18-i)][max(0,18-j)]
    if i>=max(0,18-i) and j>=max(0,18-j):
      ans=ans-G[i][j]
print(ans//2)

Solution (Python):

n = int(input())
T = 45
F = 19
a = [[0 for i in range(F)] for j in range(T)]
p = pow(10,9)
two_size = 18
five_size = 18
count = 0
for i in range(n):
    s = input()
    if '.' in s:
        index = s.index('.')
        s += '0' * (  9 - (len(s) - 1 - index))
        s = s.replace('.','')
    else :
        s += '0' * 9
    k = int(s)
    two = 0
    five = 0
    while k % 2 == 0:
        two += 1
        k //= 2
    while k % 5 == 0:
        five += 1
        k //= 5
    t, f = two_size - two, five_size - five
    for x in range(t, T):
        for y in range(f, F):
            count += a[x][y]
    a[two][five] += 1
print(count)

Solution (Python):
import math
def prime2(x):
  cnt = 0
  while x % 2 == 0:
    x //= 2
    cnt += 1
  return cnt
def prime5(x):
  cnt = 0
  while x % 5 == 0:
    x //= 5
    cnt += 1
  return cnt


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

D = [[0] * 3 for _ in range(N)]

M2 = 0
M5 = 0
Md = 0

cnt = 0
for x in A:
  t = x.find(".")
  d = 9
  if t != -1:
    for i in range(t):
      x = x.rstrip("0")
    d -= (len(x) - t - 1)
    x = x.replace(".", "")
  p2 = prime2(int(x))
  p5 = prime5(int(x))
  n = min(p2, p5)
  p2 -= n
  p5 -= n
  d += n
  D[cnt] = [p2, p5, d]
  cnt += 1
  M2 = max(M2, p2)
  M5 = max(M5, p5)
  Md = max(Md, d)

Md += 1
M = min(M2, M5) + 1
L = [[[0] * M for _ in range(2)] for _ in range(Md)]

ans = 0
for i in range(N):
  p2, p5, d = D[i]
  if p2 == 0:
    n = 1
    t = p5
  else:
    n = 0
    t = p2
  for j in range(Md):
    for k in range(M):
      if d + j + min(t, k) >= 18:
        ans += L[j][1 - n][k]
      if d + j >= 18:
        ans += L[j][n][k]
  L[d][n][min(t, M - 1)] += 1

print(ans)

Solution (Python):
import sys
import decimal
import numpy as np
input = sys.stdin.readline

N = int(input())
A = []
C2 = np.array([[0 for j in range(30)] for i in range(14)])  
C5 = np.array([[0 for j in range(30)] for i in range(14)])
C10 = np.zeros(14)
for _ in range(N):
    i = decimal.Decimal(input())
    c10, c2, c5 = 0, 0, 0
    while i % 1 != 0:
        c10 -= 1
        i *= 10
    while i % 10 == 0:
        c10 += 1
        i /= 10
    while i % 2 == 0:
        c2 += 1
        i /= 2
    while i % 5 == 0:
        c5 += 1
        i /= 5
    c2 = min(c2, 30)
    c5 = min(c5, 30)
    A.append((c10, c2, c5))
    C2[c10+9][c2] += 1
    C5[c10+9][c5] += 1
    C10[c10+9] += 1

ans = 0
for i in range(14):
    ans += C10[i]*np.sum(C10[18-i:])
    if i >= 9:
        ans -= C10[i]
    for j in range(18-i):
        if j >= 14:
            continue
        for k in range(1, 30):
            shouldhave = 18 - i - j
            if k >= shouldhave:
                ans += C2[i][k] * np.sum(C5[j][shouldhave:])
                ans += C5[i][k] * np.sum(C2[j][shouldhave:])

print(int(ans//2))

Solution (Python):

import sys
input = sys.stdin.readline
import math

n = int(input())
a_top = [[], []]
a_base = [[], []]
for _ in range(n):
    s = input().rstrip()
    if "." not in s:
        top = int(s)
        base = 1
    else:
        dot = s.index(".")
        length = len(s)
        lower_num = len(s) - dot - 1
        top = int(s.replace(".", ""))
        base = pow(10, lower_num)
    gcd = math.gcd(top, base)
    top = top // gcd
    base = base // gcd
    twos = 0
    fives = 0
    while top % 2 == 0:
        twos += 1
        top //= 2
    while top % 5 == 0:
        fives += 1
        top //= 5
    a_top[0].append(twos)
    a_top[1].append(fives)
    twos = 0; fives = 0
    while base % 2 == 0:
        twos += 1
        base //= 2
    while base % 5 == 0:
        fives += 1
        base //= 5
    a_base[0].append(twos)
    a_base[1].append(fives)

nums = dict()
offset = 16
field = [[0] * 35 for _ in range(35)]
for tt, tf, bt, bf in zip(a_top[0], a_top[1], a_base[0], a_base[1]):
    if tt - bt > 15:
        twos = 15
    else:
        twos = tt - bt
    if tf - bf > 15:
        fives = 15
    else:
        fives = tf - bf
    field[twos + offset][fives + offset] += 1

single = 0
double = 0
for i in range(35):
    for j in range(35):
        for k in range(35):
            for l in range(35):
                if i == k and j == l:
                    if i - offset + k - offset >= 0 and j - offset + l - offset >= 0:
                        double += field[i][j] * (field[i][j] - 1)
                else:
                    if i - offset + k - offset >= 0 and j - offset + l - offset >= 0:
                        double += field[i][j] * field[k][l]
print(single + double // 2)

Solution (Python):
n = int(raw_input())
G = []

for i in range(39):
    G.append([])
    for j in range(39):
        G[i].append(0)

ans = 0
    
for i in range(n):
    c2 = 0
    c5 = 0
    s = raw_input()
    if not '.' in s:
        p = int(s) * (10**18)
    else:
        a,b = s.split('.')
        x = len(b)
        p = int(a+b)*(10**(18-x))
    
    while (p%2==0):
        p/=2
        c2+=1
    while (p%5==0):
        p/=5
        c5+=1
    c2 = min(c2,36)
    c5 = min(c5,36)
    for j in range(37):
        for k in range(37):
            if (j+c2 >= 36 and k+c5 >= 36):
                ans += G[j][k]
    G[c2][c5] += 1
print ans

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(Decimal(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 math import gcd
n = int(input())
li = []
for i in range(n):
    s = input()
    if '.' in s:
        a, b = s.split('.')
        t = 10 ** len(b)
        li.append((int(a) * t + int(b), t))
    else:
        li.append((int(s), 1))
p = [[0] * 35 for _ in range(35)]
cnt = 0
for i in range(n):
    x, y = li[i]
    g = gcd(x, y)
    x //= g
    y //= g
    if y == 1:
        cnt += 1
    li[i] = x
    a1, b1 = 0, 0
    while x % 2 == 0:
        a1 += 1
        x //= 2
    while x % 5 == 0:
        b1 += 1
        x //= 5
    a2, b2 = 0, 0
    while y % 2 == 0:
        a2 += 1
        y //= 2
    while y % 5 == 0:
        b2 += 1
        y //= 5
    p[a1 - a2 + 9][b1 - b2 + 9] += 1
ans = 0
for i in range(0, 35):
    for j in range(0, 35):
        for a in range(max(0, 18 - i), 35):
            for b in range(max(0, 18 - j), 35):
                ans += p[i][j] * p[a][b]
print((ans - cnt) // 2)

Solution (Python):
from math import *



cnt = [[0] * 20 for i in range(20)]

ans = 0
for _ in range(int(input())):
    t = input().strip().split('.')
    if (len(t) > 1):
        b = int(t[0])*1000000000 + int(t[1]) * 10 ** (9 - len(t[1]))
    else:
        b = int(t[0]) * 1000000000
    x, y = 0, 0
    while (b % 2 == 0) and (x <= 18):
        x += 1
        b //= 2
    while (b % 5 == 0) and (y <= 18):
        y += 1
        b //= 5
    
    for i in range(20):
        for j in range(20):
            if (i + x >= 18) and (j + y >= 18):
                ans += cnt[i][j]
    cnt[x][y] += 1
print(ans)

Solution (Python):
import bisect as bi
n=int(input())
l=[input() for i in range(n)]
sto=[]
numl=[[0 for j in range(19)] for i in range(19)]
intcnt=0
for i in range(n):
    s=l[i]
    pal=[0,0]
    if "." not in s:
        pass
    else:
        cs=len(s)-s.index(".")-1
        pal=[-cs,-cs]
    N=int(s.replace(".",""))
    while N%5 == 0:
        N//=5
        pal[0]+=1
    while N%2 == 0:
        N//=2
        pal[1]+=1
    numl[min(18,pal[0]+9)][min(18,pal[1]+9)]+=1
    sto.append(pal)
    if pal[0]>=0 and pal[1]>=0:intcnt+=1
ans=0
accnuml=[[0 for i in range(20)] for j in range(20)]
for i in range(1,20):
    for j in range(1,20):
        accnuml[i][j]=accnuml[i][j-1]+accnuml[i-1][j]-accnuml[i-1][j-1]+numl[i-1][j-1]
for i in range(n):
    x,y=sto[i][0],sto[i][1]
    ans+=n-(accnuml[min(max(0,-x+9),18)][-1]+accnuml[-1][min(max(0,-y+9),18)]-accnuml[min(18,max(0,-x+9))][min(18,max(0,-y+9))])
print((ans-intcnt)//2)

Solution (Python):

from decimal import Decimal
def comp_index(x, p, maxim):
    low = 0
    high = maxim

    while low + 1 < high:
        mid = (low + high) // 2
        guess = x // p ** mid == x / p ** mid
        if guess:
            low = mid
        else:
            high = mid
    return low
n = int(input())
ansans = 0
max2 = 44
max5 = 19
a = [[0] * (2*max5+1) for _ in range(2*max2+1)]
a_ac = [[0] * (2*max5+1) for _ in range(2*max2+1)]
for _ in range(n):
    aratio = Decimal(input()).as_integer_ratio()
    a2 = -comp_index(aratio[1], 2, max2)
    if a2 == 0:
        a2 = comp_index(aratio[0], 2, max2)
    a5 = -comp_index(aratio[1], 5, max5)
    if a5 == 0:
        a5 = comp_index(aratio[0], 5, max5)
    a[a2][a5] += 1
    a_ac[a2][a5] += 1
    if a2 >= 0 and a5 >= 0:
        ansans -= 1
for i in range(max2, -max2-1, -1):
    for j in range(max5-1, -max5-1, -1):
        a_ac[i][j] += a_ac[i][j+1]
for j in range(max5, -max5-1, -1):
    for i in range(max2-1, -max2-1, -1):
        a_ac[i][j] += a_ac[i+1][j]
for i in range(-max2, max2+1):
    for j in range(-max5, max5+1):
        ansans += a[i][j] * a_ac[-i][-j]



print(ansans//2)

Solution (Python):
class BIT:
    def __init__(self, n):
        
        self.BIT = [0] * (n + 1)
        self.n = n

    
    def query(self, idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx & (-idx)
        return res_sum

    
    def add(self, idx, x):
        while idx <= self.n:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return
def get_int(f):
    if "." not in f:
        return int(f),0
    return int(f.replace(".","")),len(f)-f.index(".")-1
n = int(input())
p = []
for i in range(n):
    a, b = get_int(input())
    c, d = 0, 0
    while a % 2 == 0:
        c += 1
        a //= 2
    while a % 5 == 0:
        d += 1
        a //= 5
    c -= b
    d -= b
    p.append((c, d))
p.sort()
now = n - 1
t = BIT(200)
ans = 0
for i in range(n):
    for j in range(now, i, -1):
        if p[i][0] + p[j][0] >= 0:
            t.add(-p[j][1] + 100, 1)
            now -= 1
        else:
            break
    if now < i:
        t.add(-p[i][1] + 100, -1)
    ans += max(0, t.query(100 + p[i][1]))

print(ans)

Solution (Python):
N = int(input())
M = [[0]*20 for _ in range(20)]
M2 = [[0]*20 for _ in range(20)]

for _ in range(N):
    A = input()
    x = 0
    decLen = 0

    if '.' in A:
        p = A.index('.')
        decLen = len(A) - p - 1
        x = int(A[:p])*10**decLen + int(A[p+1:])
    else:
        x = int(A)

    f2, f5 = -decLen, -decLen
    while(x%2 == 0):
        x /= 2
        f2 += 1

    while(x%5 == 0):
        x /= 5
        f5 += 1

    f2 = min(f2, 9)
    f5 = min(f5, 9)

    M[f2+9][f5+9] += 1



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


ans = 0
for i in range(19):
    for j in range(19):



        ans += M[i][j]*M2[18-i][18-j]
        if i >= 9 and j >= 9:
            ans -= M[i][j]

print(ans//2)

Solution (Python):
from itertools import product
from collections import defaultdict
inpl = lambda: list(map(int,input().split()))
N = int(input())
X = defaultdict(int)
for _ in range(N):
    S = input()
    if '.' in S:
        S = S.rstrip('0')
        S = S.rstrip('.')
    if '.' in S:
        T, U = S.split('.')
        m = len(U)
        p = q = -m
        a = int(T+U)
    else:
        p = q = 0
        a = int(S)
    while a % 2 == 0 and p < 9:
        p += 1
        a //= 2
    while a % 5 == 0 and q < 9:
        q += 1
        a //= 5
    X[(p,q)] += 1

ans = 0
for p in range(-9,10):
    for q in range(-9,10):
        for s in range(-9,10):
            for t in range(-9,10):
                if p == s and q == t:
                    if p >= 0 and q >= 0:
                        ans += X[(p,q)] * (X[(p,q)]-1)
                elif p + s >= 0 and q + t >= 0:
                    ans += X[(p,q)] * X[(s,t)]

print(ans//2)

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




def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


import math
from collections import defaultdict

def main():
	n=II()
	
	
	d=defaultdict(int)

	for _ in range(n):
		x=float(input())
		x*=10**9
		x=int(x+0.5)
		g=math.gcd(x,10**9)
		
		a=math.gcd(x//g,10**9)
		b=10**9//g
		
		
		d[(a,b)]+=1
	

	ans=0

	for k,v in d.items():
		for kk,vv in d.items():
			if k!=kk:
				if (k[0]*kk[0])%(k[1]*kk[1])==0:
					
					ans+=v*vv


	ans//=2

	for k,v in d.items():
		if k[1]==1:
			ans+=v*(v-1)//2

	print(ans)





















if __name__ == "__main__":
	main()

Solution (Python):
import sys
import math
import bisect

def query_value(s):
    
    pos = s.find('.')
    if (pos == -1):
        return int(s) * 10 ** 9
    ans = int(s[:pos])
    
    for i in range(pos + 1, pos + 10):
        
        
        if i >= len(s):
            ans *= 10
        else:
            
            ans = ans * 10 + ord(s[i]) - ord('0')
            
    return ans

def main():
    n = 18
    A = []
    for i in range(2*n):
        A.append([0] * (2*n))
    
    for _ in range(int(input())):
        a = query_value(input())
        
        p2 = 0
        p5 = 0
        while a % 2 == 0:
            p2 += 1
            a /= 2
        while a % 5 == 0:
            p5 += 1
            a /= 5
        A[p2][p5] += 1
        
    ans = 0
    for x1 in range(2*n):
        for y1 in range(2*n):
            for x2 in range(2*n):
                for y2 in range(2*n):
                    if x1 == x2 and y1 == y2:
                        if A[x1][y1] > 0 and x1 + x2 >= n and y1 + y2 >= n:
                            
                            ans += A[x1][y1] * (A[x2][y2] - 1)
                            
                    else:
                        if A[x1][y1] > 0 and A[x2][y2] > 0 and x1 + x2 >= n and y1 + y2 >= n:
                            
                            ans += A[x1][y1] * A[x2][y2]
                            
    ans //= 2
    print(ans)
    '''
    for i in range(n):
        print('A[%d]: %s' % (i, str(A[i])))
    '''

if __name__ == "__main__":
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve0(N, AS):
    ret = 0
    for i in range(N):
        for j in range(i + 1, N):
            if AS[i] * AS[j] % 1000000000_000000000 == 0:
                
                ret += 1
    return ret


def solve1(N, AS):
    ret = 0
    P2 = []
    P5 = []
    for i in range(N):
        p2 = 0
        p5 = 0
        x = AS[i]
        while x % 2 == 0:
            p2 += 1
            x //= 2
        while x % 5 == 0:
            p5 += 1
            x //= 5
        P2.append(p2)
        P5.append(p5)
    
    for i in range(N):
        for j in range(i + 1, N):
            if P2[i] + P2[j] > 17 and P5[i] + P5[j] > 17:
                
                ret += 1
    return ret


def solve(N, AS):
    import numpy as np
    ret = 0
    P2 = []
    P5 = []
    P = np.zeros((20, 20), dtype=np.int)

    for i in range(N):
        p2 = 0
        p5 = 0
        x = AS[i]
        while x % 2 == 0:
            p2 += 1
            x //= 2
        while x % 5 == 0:
            p5 += 1
            x //= 5
        if p2 > 18:
            p2 = 18
        P2.append(p2)
        P5.append(p5)
        P[p2, p5] += 1

    for i in range(19, 0, -1):
        P[i - 1] += P[i]
    for i in range(19, 0, -1):
        P[:, i - 1] += P[:, i]

    for i in range(N):
        ret += P[18 - P2[i], 18 - P5[i]]
    ret -= P[9, 9]
    ret //= 2
    return ret


def main():
    
    N = int(input())
    AS = []
    for i in range(N):
        s = input().strip()
        try:
            v = int(s) * 1000000000
        except:
            s1, s2 = s.split(b".")
            s2 = s2 + b"0" * (9 - len(s2))
            v = int(s1) * 1000000000 + int(s2)
        
        AS.append(v)
    print(solve(N, AS))



T1 = """
5
7.5
2.4
17.000000001
17
16.000000000
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
3
"""

T2 = """
11
0.9
1
1
1.25
2.30000
5
70
0.000000001
9999.999999999
0.999999999
1.000000001
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
8
"""

T3 = """
12
1
5
25
125
625
3125
1.0
0.2
0.04
0.008
0.0016
0.00032
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
36
"""

T4 = """
2
1
1.0
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
1
"""

T5 = """
4
1
5
1.0
0.2
"""
TEST_T5 = """
>>> as_input(T5)
>>> main()
4
"""

T6 = """
6
1
5
25
1.0
0.2
0.04
"""
TEST_T6 = """
>>> as_input(T6)
>>> main()
9
"""

T7 = """
8
1
5
25
125
1.0
0.2
0.04
0.008
"""
TEST_T7 = """
>>> as_input(T7)
>>> main()
16
"""

T8 = """
1
8192
"""
TEST_T8 = """
>>> as_input(T8)
>>> main()
0
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Solution (Python):


import sys
readline = sys.stdin.readline
read = sys.stdin.read

n = int(readline())



"""
dp[i][j] = 2,5で何回割れるか
"""
dp = [[0]*20 for _ in range(50)]

M = 10**9
for i in range(n):
    bi = float(readline())
    ai = int(round(bi*M))
    
    c2=c5=0    
    x = ai
    while x%2==0:
        c2 += 1
        x//=2
    
    x = ai
    while x%5==0:
        c5 += 1
        x//=5
    
    
    dp[c2][c5] += 1
    

"""
dp[i][j] = 2,5で何回割れるか(50*20)
"""
acc = [dp[i][:] for i in range(50)]
for i in range(49,-1,-1):
    for j in range(19,-1,-1):
        if i != 49:
            acc[i][j] += acc[i+1][j] 
        if j != 19:
            acc[i][j] += acc[i][j+1] 
        if i != 49 and j != 19:
            acc[i][j] -= acc[i+1][j+1] 
            
ans = 0
for i in range(50):
    for j in range(20):
        ans += dp[i][j] * acc[max(0,18-i)][max(0,18-j)]
        if i >= 9 and j >= 9: ans -= dp[i][j]


print(ans//2)

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

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N = NI()
    A = [SI() for _ in range(N)]
    B = defaultdict(list)
    for a in A:
        if a.count(".") != 1:
            B[int(a)].append(1)
            continue
        ba, bb = a.split(".")
        ba = int(ba+bb)
        bb = 10**len(bb)
        g = math.gcd(ba, bb)
        ba //= g
        bb //= g
        B[ba].append(bb)

    facts = defaultdict(int)
    for ba, bbs in B.items():
        tmp = ba
        ba_fac_2 = 0
        while True:
            if tmp % 2: break
            ba_fac_2 += 1
            tmp //= 2
        tmp = ba
        ba_fac_5 = 0
        while True:
            if tmp % 5: break
            ba_fac_5 += 1
            tmp //= 5

        for bb in bbs:
            tmp = bb
            bb_fac_2 = 0
            while True:
                if tmp % 2: break
                bb_fac_2 += 1
                tmp //= 2
            tmp = bb
            bb_fac_5 = 0
            while True:
                if tmp % 5: break
                bb_fac_5 += 1
                tmp //= 5
            facts[(ba_fac_2 - bb_fac_2, ba_fac_5 - bb_fac_5)] += 1

    ans = 0
    for fact, k in list(facts.items()):

        fac2, fac5 = fact
        for i in range(-fac2, 50):
            for j in range(-fac5, 20):
                if fac2 == i and fac5 == j:
                    ans += k * (k-1)
                else:
                    ans += k * facts[(i, j)]


    print(ans//2)


if __name__ == "__main__":
    main()

Solution (Python):



import array
from bisect import *
from collections import *
from decimal import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

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


arr = [[0 for _ in range(20)] for _ in range(20)]

cnt = Counter()
N = int(input())
for n in range(N):
    s = input()
    d = Decimal(s)
    d = int(d * 1000000000)
    cnt2, cnt5 = func(d)
    
    
    cnt[(cnt2, cnt5)] += 1

    cnt2 = min(cnt2, 18)
    cnt5 = min(cnt5, 18)
    arr[cnt2][cnt5] += 1









ans = 0
for ij in range(19 * 19 - 1):
    i = ij // 19
    j = ij % 19
    for ij2 in range(ij, 19 * 19):
        i2 = ij2 // 19
        j2 = ij2 % 19

        if arr[i][j] * arr[i2][j2] == 0: continue

        if ij == ij2 and i + i2 >= 18 and j + j2 >= 18:
            ans += arr[i][j] * (arr[i][j] - 1) // 2
        else:
            if (arr[i][j] * arr[i2][j2] != 0 and i + i2 >= 18 and j + j2 >= 18):
                ans += arr[i][j] * arr[i2][j2]
print(ans)

Solution (Python):
from itertools import accumulate
N = int(input())

M = [[0] * 20 for _ in range(20)]

As = []
for _ in range(N):
    a = input()
    if '.' not in a:
        a += '.0'
    big, small = a.split('.')
    big = int(big)
    small = int((small + '000000000')[:9])
    A = big * 10 ** 9 + small

    bai2 = 0
    while A % 2 == 0:
        bai2 += 1
        A //= 2
        if bai2 >= 18:
            break
    bai5 = 0
    while A % 5 == 0:
        bai5 += 1
        A //= 5
        if bai5 >= 18:
            break
    As.append((bai2, bai5))
    M[0][0] += 1
    M[0][bai5+1] -= 1
    M[bai2+1][0] -= 1
    M[bai2+1][bai5+1] += 1


M2 = map(lambda row: list(accumulate(row)), M)
M3 = map(lambda col: list(accumulate(col)), zip(*M2))
M4 = list(zip(*M3))

ans = 0
for bai2, bai5 in As:
    ans += M4[18-bai2][18-bai5]
    if bai2 >= 9 and bai5 >= 9:
        ans -= 1
print(ans // 2)

Solution (Python):
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))


def main():
	N = int(input())
	D = defaultdict(int)
	table = [[0] * 100 for i in range(100)]
	tablesum = [[0] * 100 for i in range(100)]
	for i in range(N):
		A = input()
		num = ""
		mod5 = 0
		mod2 = 0
		for j in range(len(A)):
			if A[-1 - j] == ".":
				mod5 -= j
				mod2 -= j
			else:
				num += A[-1 - j]

		num = int(num[::-1])
		while True:
			if num % 2 == 0:
				mod2 += 1
				num = int(num // 2)
			else:
				break
		while True:
			if num % 5 == 0:
				mod5 += 1
				num = int(num // 5)
			else:
				break

		table[50 + mod2][50 + mod5] += 1
		tablesum[50 + mod2][50 + mod5] += 1
		

	ans = 0
	
	for i in range(98, -1, -1):
		for j in range(98, -1, -1):
			tablesum[i][j] += tablesum[i + 1][j]

	for i in range(98, -1, -1):
		for j in range(98, -1, -1):
			tablesum[i][j] += tablesum[i][j + 1]

	for i in range(1, 100):
		for j in range(1, 100):
			if i >= 50 and j >= 50:
				ans += table[i][j] * (tablesum[100 - i][100 - j] - table[i][j])
			else:
				ans += table[i][j] * tablesum[100 - i][100 - j]
			
				
				

	for i in range(50, 100):
		for j in range(50, 100):
			ans += (table[i][j] - 1) * table[i][j]

	
	ans = int(ans // 2)
	print(ans)


if __name__ == '__main__':
	main()

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

n = int(input())

memo = [[0 for i in range(19)] for j in range(19)]
for i in range(n):
    ai = input().rstrip('\n')
    if '.' in ai:
        a1, a2 =  ai.split('.')
        a2 = a2 + '000000000'
        ai = a1 + a2[:9]
    else:
        ai = ai + '000000000'
    ai = int(ai)
    c2 = 0
    c5 = 0
    while True:
        if ai % 2 or c2 == 18:
            break
        ai = ai // 2
        c2 += 1
    while True:
        if ai % 5 or c5 == 18:
            break
        ai = ai // 5
        c5 += 1
    memo[c2][c5] += 1

ans1 = 0
ans2 = 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 or j != l:
                        ans2 += memo[i][j] * memo[k][l]
                    else:
                        ans1 += max(memo[i][j] * (memo[k][l]-1), 0)

print(ans2 // 2 + ans1 // 2)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
def factor(n, m=None):
    
    arr = defaultdict(int)
    temp = n



    M = 6
    for i in range(2, M):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt

    return arr

n = int(input())
a = [None]*n
m = [[0]*19 for _ in range(19)]
ab = [None]*n
for i in range(n):
    s = input()
    if "." in s:
        ind = s.index(".")
        vv = len(s) - s.index(".") - 1
        v = int(s[:ind])*10**(vv) + int(s[(ind+1):])
        v *= 10**(9-vv)
    else:
        v = int(s)*10**9
    d = factor(v, 5)
    d.setdefault(2,0)
    d.setdefault(5,0)
    a,b = max(0, 18-d[2]), max(0, 18-d[5])
    m[a][b] += 1
    ab[i] = (d[2],d[5])
def cumsum2(v):
    
    h,w = len(v), len(v[0])
    v.insert(0, [0]*w)
    for l in v:
        l.insert(0, 0)
    for i in range(1,h+1):
        for j in range(1,w+1):
            v[i][j] = v[i-1][j] + v[i][j-1] - v[i-1][j-1] + v[i][j]
    return v
m = cumsum2(m)
ans = 0
for a,b in ab:

    ans += m[min(19,a+1)][min(19,b+1)]
    if a>=9 and b>=9:
        ans -= 1
print(ans//2)

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

n=int(input())
a=[]
for i in range(n):
    x=input().rstrip()
    if '.' in x:
        y=x.split('.')
        x=int(y[0])*10**9+int(y[1])*10**(9-len(y[1]))
    else:
        x=int(x)*10**9
    a.append(x)

b=[]
for i in a:
    x=i
    count2=0
    while x%2==0:
        x=x//2
        count2+=1
    count5 = 0
    while x % 5 == 0:
        x = x // 5
        count5 += 1

    b.append((count2,count5))

imos=[[0]*50 for i in range(50)]

for i in b:
    imos[0][0]+=1
    imos[i[0]+1][0]-=1
    imos[0][i[1]+1]-=1
    imos[i[0]+1][i[1]+1]+=1

for i in range(49):
    for j in range(49):
        imos[i][j+1]+=imos[i][j]
for j in range(49):
    for i in range(49):
        imos[i+1][j]+=imos[i][j]

ans=0
for i in b:
    x=18-i[0]
    y=18-i[1]
    x=max(x,0)
    y=max(y,0)
    ans+=imos[x][y]

for i in b:
    if i[0]*2>=18 and i[1]*2>=18:
        ans-=1

ans=ans//2
print(ans)