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



Sample input:
5
7.5
2.4
17.000000001
17
16.000000000


Sample output:
3

Submission status: Accepted

Solution code:

N = int(input())

bucket = dict()

def keyGen(num,den=1):
	c2 = 0
	c5 = 0
	while num%2==0:
		c2+=1
		num/=2
	while den%2==0:
		c2-=1
		den/=2
	while num%5==0:
		c5+=1
		num/=5
	while den%5==0:
		c5-=1
		den/=5
	return (c2,c5)

def addItem(d,key1):
	if key1 in d:
		d[key1]+=1
	else:
		d[key1]=1

for _ in range(N):
	theNumber = input()
	dpoint = theNumber.find('.')
	if(dpoint>-1):
		a=int(theNumber[:dpoint])
		lenOfDen = len(theNumber[1+dpoint:])
		b=int(theNumber[1+dpoint:])
		num = a*10**lenOfDen+b
		den = 10**lenOfDen
		addItem(bucket,keyGen(num,den))
	else:
		addItem(bucket,keyGen(int(theNumber)))

s=0
for it in bucket:
	x1 = it[0]
	y1 = it[1]
	r1 = bucket[it]
	for it2 in bucket:
		x2 = it2[0]
		y2 = it2[1]
		r2 = bucket[it2]
		if x1+x2>=0 and y1+y2>=0:
			if(it<it2):
				s+=r1*r2
			elif(it==it2):
				s+=(r1*(r1-1))//2

print(s)

Submission status: Accepted

Solution code:
N=int(input())
A=[input() for i in range(N)]
d=[[0]*50 for i in range(50)]
div=[]
for a in A:
    if '.' in a:
        i=a.index('.')
        n=int(a[:i])*10**9+int(a[i+1:]+'0'*(10-len(a)+i))
    else:
        n=int(a)*10**9
    t,f=0,0
    while n%2==0:
        n//=2
        t+=1
    while n%5==0:
        n//=5
        f+=1
    d[t+1][f+1]+=1
    div.append((t,f))
for i in range(49):
    for j in range(49):
        d[i+1][j+1]+=d[i+1][j]+d[i][j+1]-d[i][j]
r=0
for t,f in div:
    r+=d[-1][-1]-d[-1][max(0,18-f)]-d[max(0,18-t)][-1]+d[max(0,18-t)][max(0,18-f)]
    if max(0,18-t)<=t and max(0,18-f)<=f:
        r-=1
print(r//2)

Submission status: Accepted

Solution code:
import decimal
n = int(input())

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

l = []
for i in range(n):
    x = decimal.Decimal(input())
    x *= 10**9
    x = int(x)
    
    two = 0
    while x%2 == 0:
        x //= 2
        two += 1
    five = 0
    while x%5 == 0:
        x //= 5
        five += 1
    cum[two][five] += 1
    l.append((two,five))

for i in range(48,-1,-1):
    for j in range(48,-1,-1):
        cum[i][j] += cum[i][j+1]+cum[i+1][j]-cum[i+1][j+1]

ans = 0
for i,j in l:
    x = max(18-i,0)
    y = max(18-j,0)
    if x <= i and y <= j:
        ans += cum[x][y]-1
    else:
        ans += cum[x][y]
print(ans//2)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
from decimal import *
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.readline())
def FI(): return float(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
D = defaultdict(lambda:defaultdict(int))
for j in range(n):
    a = input()
    r = len(a) - a.find(".") - 1 if "." in a else 0
    a = a.replace(".", "")
    cnt1 = -r
    cnt2 = -r
    a = int(a)
    while a % 2 == 0:
        a //= 2
        cnt1 += 1
    while a % 5 == 0:
        a //= 5
        cnt2 += 1
    D[cnt1][cnt2] += 1

ans = 0
for i in range(-20, 30):
    for k in range(-10, 15):
        for j in range(-20, 30):
            for l in range(-10, 15):
                if i + j >= 0 and k + l >= 0:
                    if i == j and k == l:
                        ans += D[i][k] * (D[j][l] - 1)
                    else:
                        ans += D[i][k] * D[j][l]

print(ans // 2)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
from decimal import *
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.readline())
def FI(): return float(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
D = defaultdict(lambda:defaultdict(int))
for j in range(n):
    a = input()
    r = len(a) - a.find(".") - 1 if "." in a else 0
    a = a.replace(".", "")
    a = int(a) * 10 ** (9 - r)
    cnt1 = 0
    cnt2 = 0
    while a % 2 == 0:
        a //= 2
        cnt1 += 1
    while a % 5 == 0:
        a //= 5
        cnt2 += 1
    D[cnt1][cnt2] += 1

ans = 0
for i in range(50):
    for j in range(25):
        for k in range(50):
            for l in range(25):
                if min(i + k, j + l) >= 18:
                    if i == k and j == l:
                        ans += D[i][j] * (D[k][l] - 1)
                    else:
                        ans += D[i][j] * D[k][l]


print(ans // 2)

Submission status: Accepted

Solution code:
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 a, b in lis:
        k = d[(a, b)]
        for x, y in lis:
            l = d[(x, y)]
            if a >= 9 and b >= 9 and (a, b) == (x, y):
                ans_0 += k * (k - 1)
            elif a + x >= 18 and b + y >= 18:
                ans_f += k * l
    print((ans_0 + ans_f) // 2)
    return


solve()

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# A - Integer Product 
n = int(input())
a = [input() for _ in range(n)]

# bi=ai*(10**9)とすると、(aiは小数第9位までの小数だからbiは整数)
# ai*ajが整数<=>bi*bj/(10**18)が整数<=>bi*bjが素因数に2を18個、5を18個持つ。
# p2[i]:biを素因数分解したときの2の数。
# p5[i]:biを素因数分解したときの5の数。
# c25[i][j]:bi...bnのうち、素因数に2をi個以上、5をj個以上持つbiの数。
# biに対して、ペアになれるのはc25[18-p2[i]][18-p5[i]]個。
# ただし、自分自身は含めないのでbiが素因数として2を9個以上、5を9個以上もつときは―1する。
# また、(bi,bj)と(bj,bi)を重複して数えてしまうので、最後に//2する。

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

for i in range(n):
  # Decimalを使ったらTLEしてしまったので、文字列操作でbiを計算する。
  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)

Submission status: Accepted

Solution code:
# A - Integer Product 
n = int(input())
a = [input() for _ in range(n)]

# bi=ai*(10**9)とすると、(aiは小数第9位までの小数だからbiは整数)
# ai*ajが整数<=>bi*bj/(10**18)が整数<=>bi*bjが素因数に2を18個、5を18個持つ。
# p2[i]:biを素因数分解したときの2の数。
# p5[i]:biを素因数分解したときの5の数。
# c25[i][j]:bi...bnのうち、素因数に2をi個以上、5をj個以上持つbiの数。
# biに対して、ペアになれるのはc25[18-p2[i]][18-p5[i]]個。
# ただし、自分自身は含めないのでbiが素因数として2を9個以上、5を9個以上もつときは―1する。
# また、(bi,bj)と(bj,bi)を重複して数えてしまうので、最後に//2する。

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

for i in range(n):
  # Decimalを使ったらTLEしてしまったので、文字列操作でbiを計算する。
  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)

Submission status: Accepted

Solution code:
# A - Integer Product 
n = int(input())
a = [input() for _ in range(n)]

# bi=ai*(10**9)とすると、(aiは小数第9位までの小数だからbiは整数)
# ai*ajが整数<=>bi*bj/(10**18)が整数<=>bi*bjが素因数に2を18個、5を18個持つ。
# p2[i]:biを素因数分解したときの2の数。
# p5[i]:biを素因数分解したときの5の数。
# c25[i][j]:bi...bnのうち、素因数に2をi個以上、5をj個以上持つbiの数。
# biに対して、ペアになれるのはc25[18-p2[i]][18-p5[i]]個。
# ただし、自分自身は含めないのでbiが素因数として2を9個以上、5を9個以上もつときは―1する。
# また、(bi,bj)と(bj,bi)を重複して数えてしまうので、最後に//2する。

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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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)

Submission status: Accepted

Solution code:
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
    #print(n,"check:{},{}".format(ind2,ind5))

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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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)
    # a = int(a * (10**9))
    # print(a)
    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)

Submission status: Accepted

Solution code:
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])
        #print(x,L)
        TWO-=L
        FIVE-=L

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

        #print(x)

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

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

        #print(TWO,FIVE)

    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 l in LIST:
#    print(*l)

#print()

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]

#for l in LIST:
#    print(*l)

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(x,y,ANS)

print(ANS//2)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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
    # x10^9
    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
    #if 0<=cnt5+o<23 and 0<=cnt2+o<23:
    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)
  #mp[o,o]+=10
  #print(mp)

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)