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
def main(N, A):
    m = [[0] * 19 for _ in range(19)]
    Ad = []
    for a in A:
        p = a.index('.') if a.count('.') > 0 else len(a) - 1
        l = len(a) - p - 1
        n = int(a.replace('.', '') + '0' * (9 - l))
        if n == 0:
            m[18][18] += 1
            Ad.append((18, 18))
            continue
        d2, d5 = 0, 0
        while n % 2 == 0:
            d2 += 1
            n //= 2
        while n % 5 == 0:
            d5 += 1
            n //= 5
        d2 = min(d2, 18)
        d5 = min(d5, 18)
        m[d2][d5] += 1
        Ad.append((d2, d5))
    for i in range(18, 0, -1):
        for j in range(19):
            m[i - 1][j] += m[i][j]
    for i in range(19):
        for j in range(18, 0, -1):
            m[i][j - 1] += m[i][j]
    ans = 0
    for d2, d5 in Ad:
        dd2, dd5 = 18 - d2, 18 - d5
        ans += m[dd2][dd5]
        if d2 >= dd2 and d5 >= dd5:
            ans -= 1
    print(ans // 2)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    A = [input().rstrip() for _ in range(N)]
    main(N, A)

Solution (Python):
def solve():
    from collections import defaultdict
    from fractions import Fraction
    n = int(input())
    d = defaultdict(int)
    for i in range(n):
        x = Fraction(input())
        x *= 10 ** 9
        cnt2, cnt5 = 0, 0
        while x % 5 == 0:
            x //= 5
            cnt5 += 1
        while x % 2 == 0:
            x //= 2
            cnt2 += 1
        d[(cnt2, cnt5)] += 1
    lis = list(d)
    ans_0 = 0
    ans_f = 0
    for i, (a, b) in enumerate(lis):
        k = d[(a, b)]
        if a >= 9 and b >= 9:
            ans_0 += k * (k - 1) // 2
        for x, y in lis[i + 1:]:
            l = d[(x, y)]
            if a + x >= 18 and b + y >= 18:
                ans_f += k * l
    print(ans_0 + ans_f)
    return


solve()

Solution (Python):





"""
"""

from collections import defaultdict
import bisect

import sys
input = sys.stdin.readline
from decimal import *
from collections import Counter


def solve(n):
    cnt = Counter()
    n_int = 0
    for _ in range(n):
        getcontext().prec = 22
        a = input().rstrip()
        da = Decimal(a)
        ia = int(da.shift(9))
        
        if ia%10**9 == 0:
            n_int += 1
        pmul_2 = 0
        pmul_5 = 0
        ia2 = ia
        while ((ia2 & 1) == 0 and pmul_2 < 18): 
            ia2 = ia2 >> 1
            pmul_2 += 1
        ia5 = ia
        while 1:
            if (ia5 % 5 ==0 and pmul_5 < 18):
                pmul_5 += 1
                ia5 = ia5//5
            else:
                break
        cnt[(pmul_2,pmul_5)] += 1
    ans = 0
    
    for pm2_1 in range(0,19):
        for pm2_2 in range(18-pm2_1,19):
            for pm5_1 in range(0,19):
                for pm5_2 in range(18-pm5_1,19):
                    ans += cnt[(pm2_1,pm5_1)]*cnt[(pm2_2,pm5_2)]
    ans -= n_int
    ans = ans//2
    
    print(ans)
                






def main():
    n = int(input())
    solve(n)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 9

def main():
    N = int(input())
    A = [[0]*19 for _ in range(19)]
    power10 = [1]
    for _ in range(9):
        power10.append(power10[-1] * 10)
    for i in range(N):
        s = input()
        a = s.split('.')
        if len(a) > 1:
            s = a[0] + a[1]
            power = power10[9 - len(a[1])]
        else:
            s = a[0]
            power = power10[9]
        x = int(s) * power
        cnt1 = 0
        while x > 0 and x%2 == 0:
            x //= 2
            cnt1 += 1
        cnt2 = 0
        while x > 0 and x%5 == 0:
            x //= 5
            cnt2 += 1
        if cnt1 >= 18 and cnt2 >= 18:
            A[18][18] += 1
        elif cnt1 >= 18:
            A[18][cnt2] += 1
        elif cnt2 >= 18:
            A[cnt1][18] += 1
        else:
            A[cnt1][cnt2] += 1
    
    ans = 0
    for i in range(19):
        for j in range(19):
            for k in range(18 - i,19):
                for l in range(18 - j,19):
                    if i == k and j == l:
                        ans += A[i][j] * (A[k][l] - 1)
                    else:
                        ans += A[i][j] * A[k][l]
    print(ans//2)
if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
from decimal import Decimal

N = int(input())

nums = [Decimal(input()) for _ in range(N)]

two_fives = []


for i, num in enumerate(nums):
    int_converted = int(num * (10**9))
    
    two_div_count = 0
    while int_converted % 2 == 0:
        two_div_count += 1
        int_converted //= 2
    
    five_div_count = 0
    while int_converted % 5 == 0:
        five_div_count += 1
        int_converted //= 5

    two_fives.append((two_div_count,five_div_count))


ok_count = 0

two_five_exists = np.zeros((19,19), dtype=int)

for i in range(N):    
    two_count, five_count = two_fives[i]
    two_count = min(18, two_count)
    five_count = min(18, five_count)
    ok_count += two_five_exists[two_count, five_count]

    two_pair = 18 - two_count
    five_pair = 18 - five_count
    two_five_exists[two_pair:, five_pair:] += 1

print(ok_count)

Solution (Python):

n = int(input())
a = [input() for _ in range(n)]










p2 = [0 for _ in range(n)]
p5 = [0 for _ in range(n)]

for i in range(n):
  
  if '.' in a[i]:
    bi = int(a[i].replace('.','')+'0'*(9-(len(a[i])-a[i].index('.')-1)))
  else:
    bi = int(a[i])*(10**9)
  c = 0
  while(bi%2 == 0):
    c += 1
    bi //= 2
  p2[i] = c
  c = 0
  while(bi%5 == 0):
    c += 1
    bi //= 5
  p5[i] = c

c25 = [[0 for _ in range(50)] for _ in range(50)]
for i in range(n):
  c25[p2[i]][p5[i]] += 1
for i in range(48,-1,-1):
  for j in range(48,-1,-1):
    c25[i][j] += c25[i+1][j]+c25[i][j+1]-c25[i+1][j+1]

ans = 0
for i in range(n):
  ans += c25[max(18-p2[i],0)][max(18-p5[i],0)]
  if p2[i] >= 9 and p5[i] >= 9:
    ans -= 1
print(ans//2)

Solution (Python):

n = int(input())
a = [input() for _ in range(n)]










p2 = [0 for _ in range(n)]
p5 = [0 for _ in range(n)]

for i in range(n):
  
  if '.' in a[i]:
    bi = int(a[i].replace('.','')+'0'*(9-(len(a[i])-a[i].index('.')-1)))
  else:
    bi = int(a[i])*(10**9)
  c = 0
  while(bi%2 == 0 and c < 18):
    c += 1
    bi //= 2
  p2[i] = c
  c = 0
  while(bi%5 == 0 and c < 18):
    c += 1
    bi //= 5
  p5[i] = c

c25 = [[0 for _ in range(20)] for _ in range(20)]
for i in range(n):
  c25[p2[i]][p5[i]] += 1
for i in range(18,-1,-1):
  for j in range(18,-1,-1):
    c25[i][j] += c25[i+1][j]+c25[i][j+1]-c25[i+1][j+1]

ans = 0
for i in range(n):
  ans += c25[18-p2[i]][18-p5[i]]
  if p2[i] >= 9 and p5[i] >= 9:
    ans -= 1
print(ans//2)

Solution (Python):

n = int(input())
a = [input() for _ in range(n)]










p2 = [0 for _ in range(n)]
p5 = [0 for _ in range(n)]

for i in range(n):
  if '.' in a[i]:
    bi = int(a[i].replace('.','')+'0'*(9-(len(a[i])-a[i].index('.')-1)))
  else:
    bi = int(a[i])*(10**9)
  c = 0
  while(bi%2 == 0 and c < 18):
    c += 1
    bi //= 2
  p2[i] = c
  c = 0
  while(bi%5 == 0 and c < 18):
    c += 1
    bi //= 5
  p5[i] = c

c25 = [[0 for _ in range(20)] for _ in range(20)]
for i in range(n):
  c25[p2[i]][p5[i]] += 1
for i in range(18,-1,-1):
  for j in range(18,-1,-1):
    c25[i][j] += c25[i+1][j]+c25[i][j+1]-c25[i+1][j+1]

ans = 0
for i in range(n):
  ans += c25[18-p2[i]][18-p5[i]]
  if p2[i] >= 9 and p5[i] >= 9:
    ans -= 1
print(ans//2)

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 = 0
  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):
def ind(b,n):
    res=0
    while n%b==0:
        res+=1
        n//=b
    return res

import sys

input=sys.stdin.readline

N=int(input())
data=[[0 for i in range(20)] for j in range(75)]
for i in range(N):
    n=input().rstrip().split(".")
    if len(n)==1:
        a=int(n[0])
        a*=10**9
        ind2=ind(2,a)
        ind5=ind(5,a)
        data[ind2][ind5]+=1
    else:
        a,b=int(n[0]),int(n[1])
        a=a*10**9+b*10**(9-len(n[1]))
        ind2=ind(2,a)
        ind5=ind(5,a)
        data[ind2][ind5]+=1
    

ans=0
for i in range(75):
    for j in range(20):
        for k in range(75):
            for l in range(20):
                if i+k>=18 and j+l>=18:
                    if (i,j)!=(k,l):
                        ans+=data[i][j]*data[k][l]
                    else:
                        ans+=0
                        ans+=data[i][j]**2-data[i][j]

print(ans//2)

Solution (Python):
from collections import defaultdict
N = int(input())

memo = defaultdict(int)

for _ in range(N):
    a = input()
    if "." in a:
        x, y = a.split(".")
        x = int(x) * (10 ** 9)
        y = y[::-1]
        y = y.zfill(9)
        y = y[::-1]
        y = int(y)
        val = x + y
    else:
        val = int(a) * (10 ** 9)
    c2 = 0
    c5 = 0
    while val and val % 2 == 0:
        val //= 2
        c2 += 1
    while val and val % 5 == 0:
        val //= 5
        c5 += 1
    memo[(c2, c5)] += 1

ans = 0
keys = list(memo.keys())
size = len(keys)

for i in range(size):
    a, b = keys[i]
    v1 = memo[(a, b)]
    for j in range(i, size):
        c, d = keys[j]
        v2 = memo[(c, d)]
        if a + c < 18 or b + d < 18:
            continue
        if i == j:
            ans += v1 * (v1 - 1) // 2
        else:
            ans += v1 * v2
print(ans)

Solution (Python):
import math
n = int(input())

alist = []
for i in range(n):
    alist.append(int(round(float(input())*10**9)))

def two_five_power(n):
    a = 0
    b = 0
    while n % 2 == 0:
        n /=2
        a += 1
    while n % 5 == 0:
        n /= 5
        b += 1
    return (a,b)

ab_dict = dict()
for i in range(n):
    ab = two_five_power(alist[i])
    if ab in ab_dict:  
        ab_dict[ab] += 1
    else:
        ab_dict[ab] = 1

prev = 0
count = 0
for one in ab_dict:
    for two in ab_dict:
        if one[0] + two[0] >= 18 and one[1] + two[1] >= 18:    
            if one < two:
                count += ab_dict[one] * ab_dict[two]
            else: 
                if one == two:
                    count += ab_dict[one] * (ab_dict[two]-1) // 2

print(count)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



from decimal import getcontext, Decimal
getcontext().prec = 15

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

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

N = I()
A = []
for i in range(N):
    A.append(int(10**9*Decimal(input())))

counter = [[0]*30 for _ in range(50)]
for i in range(N):
    c2 = count2(A[i])
    c5 = count5(A[i])
    counter[c2][c5] += 1

same = 0
diff = 0
for i in range(50):
    for j in range(30):
        if counter[i][j]:
            for p in range(18-i,50):
                for q in range(18-j,30):
                    if i != p or j != q:
                        diff += counter[i][j]*counter[p][q]
                    else:
                        same += counter[i][j]*(counter[p][q]-1)//2

print(diff//2+same)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



from decimal import getcontext, Decimal

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

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

N = I()
A = []
for i in range(N):
    A.append(int(10**9*Decimal(input())))

counter = [[0]*30 for _ in range(50)]
for i in range(N):
    c2 = count2(A[i])
    c5 = count5(A[i])
    counter[c2][c5] += 1

same = 0
diff = 0
for i in range(50):
    for j in range(30):
        if counter[i][j]:
            for p in range(18-i,50):
                for q in range(18-j,30):
                    if i != p or j != q:
                        diff += counter[i][j]*counter[p][q]
                    else:
                        same += counter[i][j]*(counter[p][q]-1)//2

print(diff//2+same)

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

n = int(input())
a = []
for _ in range(n):
    sa = input().strip()
    tmp = 0
    for i in range(len(sa)):
        if sa[i] == '.':
            break
        tmp = tmp * 10 + int(sa[i])
    i += 1
    for j in range(i, i + 9):
        if j < len(sa):
            tmp = tmp * 10 + int(sa[j])
        else:
            tmp *= 10
    a.append(tmp)

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

div25.sort(key=lambda x: (-x[1], -x[0]))

plot = [[0 for _ in range(19)] for _ in range(19)]
ans = 0
for d25 in div25:
    rem2, rem5 = max(0, 18 - d25[0]), max(0, 18 - d25[1])
    for j in range(rem5, 19):
        for k in range(rem2, 19):
            ans += plot[j][k]
    plot[min(18, d25[1])][min(18, d25[0])] += 1
print(ans)

Solution (Python):
import numpy as np

n = int(input())

ans = 0
ma = np.zeros((19, 19), dtype=np.int)
for _ in range(n):
    aa = input().split('.')
    a2, a5 = 0, 0
    if len(aa) == 1:
        aaa = int(aa[0])
        a2, a5 = 9, 9
    else:
        aaa = int(aa[0]) * 10 ** 9
        aaa += int(aa[1])*10**(9-len(aa[1]))

    while aaa % 2 == 0:
        a2 += 1
        aaa = aaa // 2
    while aaa % 5 == 0:
        a5 += 1
        aaa = aaa // 5

    a2, a5 = min(a2, 18), min(a5, 18)

    oa2, oa5 = 18-a2, 18-a5
    ans += ma[oa2, oa5]

    ma[:a2+1, :a5+1] += 1

print(ans)

Solution (Python):
import sys
from decimal import Decimal
def input(): return sys.stdin.readline().rstrip()


def twofive(x):
    cnt = 0
    while x % 2 == 0:
        x = x//2
        cnt += 20
    while x % 5 == 0:
        x = x//5
        cnt += 1
    return cnt


def main():
    n = int(input())
    bag = [0]*1000
    ans = 0
    for _ in range(n):
        bag[twofive(int(Decimal(input())*10**9))] += 1
    for i in range(999):
        for j in range(i+1, 1000):
            i2 = i//20
            i5 = i % 20
            j2 = j//20
            j5 = j % 20
            if i2+j2 >= 18 and i5+j5 >= 18:
                ans += bag[i]*bag[j]
    for k in range(1000):
        if k//20 >= 9 and k % 20 >= 9:
            ans += (bag[k]*(bag[k]-1))//2

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import sys 
from collections import Counter
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
cnt = Counter()

for i in range(N):
    cnt_2 = 0
    cnt_5 = 0
    a = float(readline())
    a = int(a * (10**9)+0.5)

    while a % 2 == 0:
        a //= 2
        cnt_2 += 1
    while a % 5 == 0:
        a //= 5
        cnt_5 += 1
    cnt[(cnt_2-9,cnt_5-9)] += 1
    
ans = 0
for (x1,y1),c1 in cnt.items():
    for (x2,y2),c2 in cnt.items():
        if x1+x2 >= 0 and y1+y2 >= 0:
            if x1 == x2 and y1 == y2:
                ans += c1*(c1-1)
            else:
                ans += c1*c2

print(ans//2)

Solution (Python):

import sys 
from collections import Counter
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
cnt = Counter()

for i in range(N):
    cnt_2 = 0
    cnt_5 = 0
    a = float(readline())
    a = round(a*10**9)
    
    
    while a % 2 == 0:
        a //= 2
        cnt_2 += 1
    while a % 5 == 0:
        a //= 5
        cnt_5 += 1
    cnt[(cnt_2-9,cnt_5-9)] += 1
    
ans = 0
for (x1,y1),c1 in cnt.items():
    for (x2,y2),c2 in cnt.items():
        if x1+x2 >= 0 and y1+y2 >= 0:
            if x1 == x2 and y1 == y2:
                ans += c1*(c1-1)
            else:
                ans += c1*c2

print(ans//2)

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

N=int(input())
A=[input().strip() for i in range(N)]

X=[]

for a in A:
    TWO=0
    FIVE=0

    if "." in a:
        x=a.split(".")
        L=len(x[1])
        
        TWO-=L
        FIVE-=L

        x=int("".join(x))

        

        while x%2==0:
            x//=2
            TWO+=1

        while x%5==0:
            x//=5
            FIVE+=1

        

    else:
        x=int(a)
        while x%2==0:
            x//=2
            TWO+=1

        while x%5==0:
            x//=5
            FIVE+=1

    X.append((TWO,FIVE))

LIST=[[0]*100 for i in range(100)]

for x,y in X:
    LIST[x+35][y+35]+=1






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

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




ANS=0

for x,y in X:
    x2=-x
    y2=-y

    if x>=x2 and y>=y2:
        ANS-=1

    ANS+=LIST[x2+35][y2+35]

    

print(ANS//2)

Solution (Python):
def numpwr(x, div):
    ans = 0
    while x%div==0:
        ans+=1
        x//=div
    return ans

n = int(input())
a = []
for i in range(n):
    a.append(input())

ints = []
for dec in a:
    loc = dec.find('.')
    need = 9
    if loc != -1:
        need = 9-(len(dec)-loc-1)
    dec = dec.replace('.', '')
    num = int(dec) * 10**need
    ints.append(num)

cnt = {}
for i in ints:
    key = (numpwr(i,2), numpwr(i,5))
    if key in cnt:
        cnt[key]+=1
    else:
        cnt[key] = 1

ans = 0
for p1 in cnt.items():
    for p2 in cnt.items():
        if p1[0][0]+p2[0][0]>=18 and p1[0][1]+p2[0][1]>=18:
            if p1 < p2:
                ans += p1[1]*p2[1]
            elif p1==p2:
                ans += p1[1]*(p1[1]-1)//2
            
print(ans)

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import Counter
def resolve():
    n = int(input())
    C = Counter()
    for _ in range(n):
        S = input()
        if '.' in S:
            a, b = S.split('.')
            two = five = -len(b)
            a = int(a + b)
        else:
            two = five = 0
            a = int(S)
        while a % 2 == 0:
            two += 1
            a //= 2
        while a % 5 == 0:
            five += 1
            a //= 5
        C[two, five] += 1

    ans = 0
    for key0, val0 in C.items():
        i0, j0 = key0
        for key1, val1 in C.items():
            i1, j1 = key1
            if i0 + i1 < 0 or j0 + j1 < 0:
                continue
            if key0 == key1:
                ans += val0 * (val0 - 1) // 2
            elif key0 < key1:
                ans += val0 * val1
    print(ans)
resolve()

Solution (Python):
N = int(input())
a = [[0 for j in range(19)] for i in range(19)]
ans=0
for _ in range(N):
    A=input()
    if A.find('.') > 0:
        count2 = 10 - len(A) + A.find('.')
        count5 = 10 - len(A) + A.find('.')
    else:
        count2 = 9
        count5 = 9
    tmp = int(A.replace('.', ''))
    while count2 < 18:
        if tmp % 2 == 0:
            count2 += 1
            tmp //= 2
        else:
            break
    while count5 < 18:
        if tmp % 5 == 0:
            count5 += 1
            tmp //= 5
        else:
            break
    for i in range(18-count2,19):
        for j in range(18-count5,19):
            ans += a[i][j]
    a[count2][count5] += 1
print(ans)

Solution (Python):
def main(n,a):
  k=60
  mp=[[0]*k for _ in range(k)]
  o=k//2
  ary=[]
  for i in range(n):
    b=list(a[i].split('.'))
    b.append('0')
    x=int(b[0])
    y=int((b[1]+'0'*9)[:9])
    x=x*pow(10,9)+y
    
    cnt5=-9
    xx=x
    while xx>1:
      if xx%5==0:
        cnt5+=1
        xx//=5
      else:
        break
    cnt2=-9
    xx=x
    while xx>1:
      if xx%2==0:
        cnt2+=1
        xx//=2
      else:
        break
    
    mp[cnt5+o][cnt2+o]+=1
    ary.append([cnt5+o,cnt2+o])

  ans=0
  for i in range(k-1,0,-1):
    for j in range(k):
      mp[j][i-1]+=mp[j][i]
  for i in range(k-1,0,-1):
    for j in range(k):
      mp[i-1][j]+=mp[i][j]
  for x,y in ary:
    if x>=o and y>=o:
      i=1
    else:
      i=0
    x-=o
    x*=-1
    x+=o
    y-=o
    y*=-1
    y+=o
    ans+=mp[x][y]-i
  print(ans//2)
  
  

n=int(input())
a=[input() for _ in range(n)]
main(n,a)

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

n = int(input())
a = []
for _ in range(n):
    sa = input().strip()
    tmp = 0
    for i in range(len(sa)):
        if sa[i] == '.':
            break
        tmp = tmp * 10 + int(sa[i])
    i += 1
    for j in range(i, i + 9):
        if j < len(sa):
            tmp = tmp * 10 + int(sa[j])
        else:
            tmp *= 10
    a.append(tmp)

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

div25.sort(key=lambda x: (-x[1], -x[0]))

plot = [[0 for _ in range(45)] for _ in range(20)]
ans = 0
for d25 in div25:
    rem2, rem5 = max(0, 18 - d25[0]), max(0, 18 - d25[1])
    for j in range(rem5, 20):
        for k in range(rem2, 45):
            ans += plot[j][k]
    plot[d25[1]][d25[0]] += 1
print(ans)

Solution (Python):
class cumsum2D:
    def __init__(self, data):
        self.N = len(data)
        self.M= len(data[0])
        self.cum = [[0] * (self.M + 1) for _ in range(self.N + 1)]
        for i in range(self.N):
            for j in range(self.M):
                self.cum[i + 1][j + 1] = self.cum[i][j + 1] + self.cum[i + 1][j] - self.cum[i][j] + data[i][j]

    def get(self,x1,y1,x2,y2):
        """
        長方形の領域 [x1,x2)*[y1,y2) の範囲内にインプットされた数字の和を取る
        """
        return self.cum[x2][y2] - self.cum[x1][y2] - self.cum[x2][y1] + self.cum[x1][y1]

def five(x):
    cnt1 = 0
    while x%5==0:
        cnt1+= 1
        x = x//5
    cnt2 = 0
    while x%2==0:
        cnt2+= 1
        x = x//2
    return (min(cnt1,18), min(cnt2,18))

def digit_lift(S, l):
    if '.' in S:
        a, b = S.split('.')
        n = int(a + b) * 10 ** (l - len(b))
    else:
        n = int(S) * 10 ** l
    return n

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

N = int(input())
Q = set()
for _ in range(N):
    A = digit_lift(input().rstrip(),9)
    x, y = five(A)
    data[x][y] += 1
    Q.add((x,y))

cum = cumsum2D(data)
res = 0
for x, y in Q:
    res += (cum.get(18-x,18-y,-1,-1)- (x>=9 and y>=9))*data[x][y]
print(res//2)

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):
from decimal import Decimal

N, *A = map(Decimal, open(0).read().split())
N = int(N)

d = {}
for a in A:
    a = int(a * (10 ** 9))
    if a == 0:
        t = (0, 0)
    else:
        x = -9
        while a % 2 == 0:
            x += 1
            a //= 2
        y = -9
        while a % 5 == 0:
            y += 1
            a //= 5
        t = (x, y)
    d.setdefault(t, 0)
    d[t] += 1


result = 0
xs = list(d.keys())
for i in range(len(xs)):
    x, y = xs[i]
    t = d[xs[i]]
    if x >= 0 and y >= 0:
        result += t * (t - 1) // 2
    for j in range(i + 1, len(xs)):
        m, n = xs[j]
        if x + m >= 0 and y + n >= 0:
            result += t * d[xs[j]]
print(result)

Solution (Python):
def conv(s):
    if s.find('.') == -1:
        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
    while a % 2 == 0:
        y += 1
        a //= 2
    return (x, y)


N, *A = open(0).read().split()
N = int(N)

d = {}
for a in A:
    t = conv(a)
    d.setdefault(t, 0)
    d[t] += 1

result = 0
xs = list(d.keys())
for i in range(len(xs)):
    x, y = xs[i]
    t = d[xs[i]]
    if x >= 0 and y >= 0:
        result += t * (t - 1) // 2
    for j in range(i + 1, len(xs)):
        m, n = xs[j]
        if x + m >= 0 and y + n >= 0:
            result += t * d[xs[j]]
print(result)

Solution (Python):
def fact2(a, b):
    c2 = 0
    c5 = 0
    while a%2 == 0:
        a //= 2
        c2 += 1
    while a%5 == 0:
        a //= 5
        c5 += 1
    return min(c2-b, 9), min(c5-b,9)

def main():
    N = int( input())
    A2 = [0]*N
    A5 = [0]*N
    AS = [0]*N
    for i in range(N):
        a = input()
        if '.' in a:
            b, c = a.split('.')
            if int(c) == 0:
                pass
            else:
                AS[i] = len(c)
                b += c
        else:
            b = a
        
        
        A2[i], A5[i] = fact2( int(b), AS[i])

    R = [ [0]*19 for _ in range(19)]
    for i in range(N):
        a, b = A5[i]+9, A2[i]+9
        R[a][b] += 1
    AR = [ [0]*19 for _ in range(19)]
    for i in range(18,-1,-1):
        for j in range(17,-1,-1):
            R[i][j] = R[i][j] + R[i][j+1]
    for j in range(19):
        for i in range(17,-1,-1):
            R[i][j] += R[i+1][j]
    ans = 0
    
    for k in range(N):
        i, j = A5[k], A2[k]
        if i <= 9 and j <= 9:
            ans += R[-i+9][-j+9]
            
        if AS[k] == 0:
            ans -= 1
    print(ans//2)






if __name__ == '__main__':
    main()

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):
import copy
import math
import time
import statistics
import math
from decimal import Decimal
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN, ROUND_DOWN


def get_int():
    return int(input())

def get_string():
    return input()

def get_int_list():
    return [int(x) for x in input().split()]

def get_string_list():
    return input().split()

def get_int_multi():
    return map(int, input().split())

def get_string_char_list():
    return list(str(input()))




'''
while (idx < n) and ():

    idx += 1
'''



def main():
    start = time.time()

    n = get_int()
    
    
    youso = []
    aite = [[0] * 20 for i in range(20)]

    ans = 0
    for i in range(0,n):
        s = input()
        wk = Decimal(s)
        wk = wk - wk.quantize(Decimal('0'), rounding=ROUND_DOWN)
        seisu = Decimal.is_zero(wk)

        if seisu:
            if '.' in s:
                s_i, s_d = s.split('.')
                s = s_i

            count2 = 0
            wk = int(s)
            for ii in range(0, 19):
                if wk % 2 == 0:
                    count2 += 1
                    wk = wk // 2
                else:
                    break

            count5 = 0
            wk = int(s)
            for ii in range(0, 19):
                if wk % 5 == 0:
                    count5 += 1
                    wk = wk // 5
                else:
                    break

            count5 = min(9, count5)
            count2 = min(9, count2)
            

        else:
            s_i, s_d = s.split('.')

            while s_d[-1] == '0':
                s_d = s_d[:-1]

            count2 = 0
            wk = int(s_i + s_d)
            for ii in range(0, 19):
                if (wk * 2) % 10 == 0:
                    wk = wk * 2 / 10
                    count2 += 1
                else:
                    break

            count5 = 0
            wk = int(s_i + s_d)
            for ii in range(0,19):
                if (wk * 5) % 10 == 0:
                    wk = wk * 5 / 10
                    count5 += 1
                else:
                    break

            count2_wk = -len(s_d) + count5
            count5 = min(9, -len(s_d) + count2)
            count2 = min(9, count2_wk)
            

        youso.append([count2, count5])
        aite[10 - count2][10 - count5] += 1
        
        
        


    

    aite2 = [[0] * 20 for i in range(20)]
    for i in range (0,20):
        for ii in range (0, 20):
            for iii in range(i, 20):
                for iiii in range(ii, 20):
                    aite2[iii][iiii] += aite[i][ii]

    
    

    
    

    ans = 0
    for i in range(0,n):
        y1 = youso[i]
        if y1[0] >= 0 and y1[1] >= 0:
            ans += aite2[10 + y1[0]][10 + y1[1]] -1
        else:
            ans += aite2[10 + y1[0]][10 + y1[1]]

    ans = ans // 2

    print(ans)
    

if __name__ == '__main__':
    main()