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:
def decomp(m):
    p2=0
    p5=0
    while m%2==0:
        m//=2
        p2+=1
    while m%5==0:
        m//=5
        p5+=1
    return p2,p5

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

KMAX = 20
#X[i][j] 2の約数をi個、5の約数をj個もつ。9以上は9でよい
X = [[0 for _ in range(KMAX)] for _ in range(KMAX)]

for a in A:
  i,j = 0,0
  wk = a
  for i in range(KMAX):
    if a%2 == 0:
      a = a // 2
    else:
      break
  for j in range(KMAX):
    if a%5 == 0:
      a = a // 5
    else:
      break
  #print(wk,i,j)
  X[i][j] += 1
  
#print(A)
#for x in X:
 # print(x)
  
cnt = 0
for i in range(KMAX):
  for j in range(KMAX):
    for k in range(KMAX):
      for l in range(KMAX):
        if i+k < 18 or j+l < 18:
          continue
        if X[i][j] * X[k][l] == 0:
          continue
        #print(i,j,k,l, X[i][j] , X[k][l])
        if i==k and j==l:
          cnt += X[i][j] * (X[i][j] - 1)
        else:
          cnt += X[i][j] * X[k][l]
print(cnt//2)

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 = 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:
# -*- coding: utf-8 -*-
import numpy as np

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

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

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

print(answer)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

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

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

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

print(answer)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

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

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

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

print(answer)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from math import gcd

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

N = INT()
K = 10**9
L = 10**18
A = [0] * N
C = Counter()
for i in range(N):
    a = float(input())
    # ここint()だと切り捨てでバグる
    A[i] = round(a * K)
    C[gcd(A[i], L)] += 1

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

# A - Integer Product

from math import gcd
from collections import Counter

def parse(s):
    """小数点付き数字列をパース"""
    p = s.find('.')
    i, f = (s[:p], s[p + 1:]) if p >= 0 else (s, '')
    n = int(i + f)    # 分子 = 小数点なし数字列
    d = 10 ** len(f)  # 分母 = 10のべき乗
    g = gcd(n, d)
    return (n // g, d // g)  # 約分して返す

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

MAX_FLEN = 9  # 小数部の長さ

def twofive(x):
    """素因数2と5の個数を返す"""
    store = {}
    for d in (2, 5):
        store[d] = 0
        while x % d == 0:
            store[d] += 1
            x //= d
    return (store[2], store[5])

frac = [twofive(n) + twofive(d) for n, d in a]
frac = [(min(MAX_FLEN, n1), min(MAX_FLEN, d1), n2, d2)
        for n1, d1, n2, d2 in frac]
count = Counter(frac)

# count[(a, b, c, d)] = a' >= a and b' >= b and c' <= c and d' <= d
#                       である (a', b', c', d') の個数

for a in range(MAX_FLEN, -1, -1):
    for b in range(MAX_FLEN, -1, -1):
        for c in range(MAX_FLEN + 1):
            for d in range(MAX_FLEN + 1):
                count[(a, b, c, d)] = (count[(a, b, c, d)]
                    + count[(a + 1, b, c, d)]
                    + count[(a, b + 1, c, d)]
                    + count[(a, b, c - 1, d)]
                    + count[(a, b, c, d - 1)]
                    - count[(a + 1, b + 1, c, d)]
                    - count[(a + 1, b, c - 1, d)]
                    - count[(a + 1, b, c, d - 1)]
                    - count[(a, b + 1, c - 1, d)]
                    - count[(a, b + 1, c, d - 1)]
                    - count[(a, b, c - 1, d - 1)]
                    + count[(a + 1, b + 1, c - 1, d)]
                    + count[(a + 1, b + 1, c, d - 1)]
                    + count[(a + 1, b, c - 1, d - 1)]
                    + count[(a, b + 1, c - 1, d - 1)]
                    - count[(a + 1, b + 1, c - 1, d - 1)])

# 数(a1, b1, c1, d1)と(a2, b2, c2, d2)の積が整数
# <-> a2 >= c1 and b2 >= d2 and c2 <= a1 and d2 <= b1

s = sum(count[(c, d, a, b)] - (1 if c == d == 0 else 0)
        for a, b, c, d in frac)
print(s // 2)

Submission status: Accepted

Solution code:
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 = input()
    b = a.split(".")
    if len(b)==1:
        a = int(a)*(10**9)
    else:
        a = int(b[0] + b[1] + (9-len(b[1]))*"0")
    two,five = waru(a,2)-9,waru(a,5)-9
    two -= 50
    five -= 50
    num[two][five] += 1
    lis[i] = [two,five]
  cum2 = [[0]*101 for _ in range(101)]
  for i in range(95,10,-1):
    for j in range(95,10,-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):
    two,five = lis[i]
    two2,five2 = -(two+50)-50,-(five+50)-50
    ans += cum2[two2][five2]
    if two+50>=0 and five+50>=0:
      ans -= 1
  return ans//2
print(solve())

Submission status: Accepted

Solution code:
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 = input()
    b = a.split(".")
    if len(b)==1:
        a = int(a)*(10**9)
    else:
        a = int(b[0] + b[1] + (9-len(b[1]))*"0")
    two,five = waru(a,2)-9,waru(a,5)-9
    two -= 50
    five -= 50
    num[two][five] += 1
    lis[i] = [two,five]
  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):
    two,five = lis[i]
    two2,five2 = -(two+50)-50,-(five+50)-50
    ans += cum2[two2][five2]
    if two+50>=0 and five+50>=0:
      ans -= 1
  return ans//2
print(solve())

Submission status: Accepted

Solution code:
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)
    two,five = waru(a,2)-9,waru(a,5)-9
    two -= 50
    five -= 50
    num[two][five] += 1
    lis[i] = [two,five]
  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):
    two,five = lis[i]
    two2,five2 = -(two+50)-50,-(five+50)-50
    ans += cum2[two2][five2]
    if two+50>=0 and five+50>=0:
      ans -= 1
  return ans//2
print(solve())

Submission status: Accepted

Solution code:
N = int(input())
A = []
for i in range(N):
    a = input()
    b = a.split(".")
    if len(b)==1:
        A.append(int(a)*(10**9))
    else:
        A.append(int(b[0] + b[1] + (9-len(b[1]))*"0"))

B = [[0]*50 for i in range(50)]
ans1 = 0
for i in range(N):
    a = A[i]
    count1 = 0
    while a%2==0:
        a//=2
        count1+=1
    count2 = 0
    while a%5==0:
        a//=5
        count2+=1
    #print(count1,count2,A[i])
    B[count1][count2] += 1
    if count1>=9 and count2>=9:
        ans1+=1

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

for i in range(50):
    for j in range(50):
        C[i+1][j+1] = B[i][j] + C[i+1][j] + C[i][j+1] - C[i][j]

#print(*C,sep="\n")
ans = 0
for i in range(50):
    for j in range(50):
        k,l = min(18,i),min(18,j)
        #if B[i][j]>0:
        #    print(B[i][j],C[21][21] + C[18-k][18-l] - C[21][18-l] - C[18-k][21],i,j)
        ans += B[i][j] * (C[50][50] + C[18-k][18-l] - C[50][18-l] - C[18-k][50])

print((ans-ans1)//2)

Submission status: Accepted

Solution code:
N=int(input())
D={}
from decimal import Decimal
B=[Decimal(input()) for _ in range(N)]
B=[int(i*10**9) for i in B]
A=[[0]*19 for i in range(19)]
for i in range(N):
  x=B[i]
  y=x
  tcnt,fcnt=0,0
  while x%2==0 and tcnt<18:
    tcnt+=1
    x=x//2
  while y%5==0 and fcnt<18:
    fcnt+=1
    y=y//5
  A[fcnt][tcnt]+=1

cnt=0
for i in range(19):
  for j in range(19):
    for k in range(19):
      for l in range(19):
        if i+k>=18 and j+l>=18:
          if i!=k and j!=l:
            d=A[i][j]
            e=A[k][l]
            p=d*e
          elif i==k and j==l:
            d=A[i][j]
            p=d*(d-1)
          else:
            d=A[i][j]
            e=A[k][l]
            p=d*e
          cnt+=p
print(cnt//2)

Submission status: Accepted

Solution code:
N=int(input())
D={}
from decimal import Decimal
A=[Decimal(input()) for _ in range(N)]
A=[int(i*10**9) for i in A]
for i in range(N):
  x=A[i]
  y=x
  tcnt,fcnt=0,0
  while x%2==0 and tcnt<18:
    tcnt+=1
    x//=2
  while y%5==0 and fcnt<18:
    fcnt+=1
    y//=5
  if (tcnt,fcnt) not in D:
    D[((tcnt,fcnt))]=1
  else:
    D[((tcnt,fcnt))]+=1

ans=0
for t1,f1 in D:
  for t2,f2 in D:
    if t1+t2>=18 and f1+f2>=18:
      if t1==t2 and f1==f2:
        ans+=D[(t1,f1)]*(D[(t1,f1)]-1)
      else:
        ans+=D[(t1,f1)]*D[(t2,f2)]
print(ans//2)

Submission status: Accepted

Solution code:
N=int(input())
D={}
from decimal import Decimal
B=[Decimal(input()) for _ in range(N)]
B=[int(i*10**9) for i in B]
A=[[0]*19 for i in range(19)]
for i in range(N):
  x=B[i]
  y=x
  tcnt,fcnt=0,0
  while x%2==0 and tcnt<18:
    tcnt+=1
    x=x//2
  while y%5==0 and fcnt<18:
    fcnt+=1
    y=y//5
  A[fcnt][tcnt]+=1

cnt=0
for i in range(19):
  for j in range(19):
    for k in range(19):
      for l in range(19):
        if i+k>=18 and j+l>=18:
          if i!=k and j!=l:
            d=A[i][j]
            e=A[k][l]
            p=d*e
          elif i==k and j==l:
            d=A[i][j]
            p=d*(d-1)
          else:
            d=A[i][j]
            e=A[k][l]
            p=d*e
          cnt+=p
print(cnt//2)

Submission status: Accepted

Solution code:
import collections
from decimal import Decimal

n = int(input())
a = [Decimal(input()) for _ in range(n)]
a = [int(i*10**9) for i in a]
MAX = 19
p_dict = collections.defaultdict(int)

for i in a:
    b_cnt = 0
    while i % 2 == 0 and b_cnt < 18:
        i //= 2
        b_cnt += 1
    f_cnt = 0
    while i % 5 == 0 and f_cnt < 18:
        i //= 5
        f_cnt += 1
    p_dict[(b_cnt, f_cnt)] += 1

ans = 0
for b1, f1 in p_dict:
    for b2, f2 in p_dict:
        if b1+b2 >= 18 and f1+f2 >= 18:
            if b1 == b2 and f1 == f2:
                ans += p_dict[(b1, f1)] * (p_dict[(b2, f2)] - 1)
            else:
                ans += p_dict[(b1, f1)] * p_dict[(b2, f2)]
print(ans//2)

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=tf-8
#

"""
"""

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))
        #print(a,ia)
        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
    #print(cnt)
    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()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.readline
ra = range
enu = enumerate


def a_int(): return int(read())


from itertools import product


# 画像でおいた自分の解説見て
N = a_int()
B = []
for _ in ra(N):
    A = read()[:-1]  # floatで扱うと誤差で死ぬ
    if '.' not in A:
        A += '.'
    for _ in range(9 - A[::-1].index('.')):
        A += '0'
    B.append(int(A[:-10] + A[-9:]))

N = []
M = []
for b in B:
    n = 0
    while ~b & 1:  # 偶数である限り
        b >>= 1
        n += 1
    N.append(n)

    m = 0
    while b % 5 == 0:  # 5で割れる限り
        b //= 5
        m += 1
    M.append(m)

cnt = [[0] * 19 for _ in ra(19)]
ans = 0
for n, m in zip(N, M):
    x = max(18 - n, 0)
    y = max(18 - m, 0)
    for i, j in product(range(x, 19), range(y, 19)):
        ans += cnt[i][j]
    # このデータをcntに追加
    cnt[min(n, 18)][min(m, 18)] += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce


# 画像でおいた自分の解説見て
N = a_int()
B = []
for _ in ra(N):
    A = read()[:-1]  # floatで扱うと誤差で死ぬ
    if '.' not in A:
        A += '.'
    for _ in range(9 - A[::-1].index('.')):
        A += '0'
    B.append(int(A[:-10] + A[-9:]))

N = []
M = []
for b in B:
    n = 0
    while ~b & 1:  # 偶数である限り
        b >>= 1
        n += 1
    N.append(n)

    m = 0
    while b % 5 == 0:  # 5で割れる限り
        b //= 5
        m += 1
    M.append(m)

cnt = [[0] * 19 for _ in ra(19)]
ans = 0
for n, m in zip(N, M):
    x = max(18 - n, 0)
    y = max(18 - m, 0)
    for i, j in product(range(x, 19), range(y, 19)):
        ans += cnt[i][j]

    # このデータをcntに追加
    cnt[min(n, 18)][min(m, 18)] += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce


# 画像でおいた自分の解説見て
N = a_int()
B = []
for _ in ra(N):
    # A = float(read()[:-1])  # floatなら小数13桁ぐらい入る
    # B.append(int(A * (10**9)))
    A = read()[:-1]
    if '.' not in A:
        A += '.'
    for _ in range(9 - A[::-1].index('.')):
        A += '0'
    B.append(int(A[:-10] + A[-9:]))

N = []
M = []
for b in B:
    n = 0
    while b % 2 == 0:  # 偶数である限り
        b >>= 1
        n += 1
    N.append(n)

    m = 0
    while b % 5 == 0:  # 5で割れる限り
        b //= 5
        m += 1
    M.append(m)

cnt = [[0] * 19 for _ in ra(19)]
ans = 0
for n, m in zip(N, M):
    x = max(18 - n, 0)
    y = max(18 - m, 0)
    for i, j in product(range(x, 19), range(y, 19)):
        ans += cnt[i][j]

    # このデータをcntに追加
    cnt[min(n, 18)][min(m, 18)] += 1

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = [round(float(input())*(10**9)) for _ in range(N)]
fac = [[0, 0] for _ in range(N)]

for i, x in enumerate(A):
    while x%2 == 0:
        x //= 2
        fac[i][0] += 1
    while x%5 == 0:
        x //= 5
        fac[i][1] += 1

acc = [[0]*51 for _ in range(51)]

for l in fac:
    n2, n5 = l
    acc[n2+1][n5+1] += 1

acc = np.array(acc, dtype=np.int64)
acc = acc.cumsum(0).cumsum(1).tolist()

ans = 0

for l in fac:
    n2, n5 = l
    n2l = max(0, 18-n2)
    n5l = max(0, 18-n5)
    ans += acc[50][50] - acc[n2l][50] - acc[50][n5l] + acc[n2l][n5l]
    if n2 >= 9 and n5 >= 9:
        ans -= 1

print(ans//2)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = []
MX = 60
li = [[0]*MX for _ in range(MX)]
for _ in range(n):
    s = input().rstrip()
    tmp = s.find('.')
    if tmp==-1:
        r = 0
        k = int(s)
    else:
        r = -(len(s)-tmp-1)
        k = int(s[:tmp]+s[tmp+1:])
    r2 = r
    while k%2==0:
        k //= 2
        r2 += 1
    r5 = r
    while k%5==0:
        k //= 5
        r5 += 1
    li[r2+10][r5+10] += 1
ans = 0
for i in range(MX):
    for j in range(MX):
        for k in range(MX):
            for l in range(MX):
                if i+k-20<0 or j+l-20<0:
                    continue
                if i==k and j==l:
                    ans += li[i][j]*(li[i][j]-1)
                else:
                    ans += li[i][j]*li[k][l]
print(ans//2)

Submission status: Accepted

Solution code:
N, *A = open(0).read().split()

S = [[0] * 21 for _ in range(21)]

ans = 0
for a in A:
    idx = a.find(".")
    if idx == -1:
        c2 = c5 = 0
    else:
        c2 = c5 = -(len(a) - idx - 1)

    a = int(a.replace(".", ""))
    while a % 2 == 0:
        c2 += 1
        a //= 2
    while a % 5 == 0:
        c5 += 1
        a //= 5
    c2 = min(c2, 10)
    c5 = min(c5, 10)
    ans += sum(S[i][j] for i in range(10 - c2, 21) for j in range(10 - c5, 21))

    S[c2 + 10][c5 + 10] += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def calc(a):
    a1, a2 = 0, 0
    if '.' in a:
        a = a.rstrip('0')
        cnt = len(a) - a.index('.') - 1
        a1, a2 = -cnt, -cnt
    a = int(a.replace('.', ''))

    while a % 2 == 0:
        a1 += 1
        a //= 2
    while a % 5 == 0:
        a2 += 1
        a //= 5
    return a1, a2

d = defaultdict(int)
N = int(input())
A = []
for _ in range(N):
    a = input()
    a1, a2 = calc(a)
    d[(a1, a2)] += 1

ans = 0
key = list(d.keys())
for i in range(len(key)):
    a1, a2 = key[i]
    v = d[(a1, a2)]
    if a1 >= 0 and a2 >= 0:
        ans += v * (v - 1) // 2
    for j in range(i + 1, len(key)):
        b1, b2 = key[j]
        if (a1 + b1) >= 0 and (a2 + b2) >= 0:
            ans += v * d[(b1, b2)]

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
def calc(x):
    c2, c5 = 0, 0
    if '.' in x:
        x = x.rstrip('0')
        cnt = len(x) - x.index('.') - 1
        c2, c5 = -cnt, -cnt
    x = int(x.replace('.', ''))
    while x % 2 == 0:
        c2 += 1
        x = x // 2
    while x % 5 == 0:
        c5 += 1
        x = x // 5
    return c2, c5
    
    
d = defaultdict(int)
n = int(input())
A = []
for _ in range(n):
    a = input()
    c2, c5 = calc(a)
    d[(c2, c5)] += 1
ans = 0
key = list(d.keys())
for i in range(len(key)):
    c2, c5 = key[i]
    v = d[(c2, c5)]
    if (c2 >= 0) & (c5 >= 0):
        ans += v * (v - 1) // 2
    for j in range(i + 1, len(key)):
        n2, n5 = key[j]
        if ((n2 + c2) >= 0) & ((n5 + c5) >= 0):
            ans += v * d[(n2, n5)]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
def calc(x):
    c2, c5 = 0, 0
    if '.' in x:
        x = x.rstrip('0')
        cnt = len(x) - x.index('.') - 1
        c2, c5 = -cnt, -cnt
    x = int(x.replace('.', ''))
    while x % 2 == 0:
        c2 += 1
        x = x // 2
    while x % 5 == 0:
        c5 += 1
        x = x // 5
    return c2, c5
    
    
d = defaultdict(int)
n = int(input())
A = []
for _ in range(n):
    a = input()
    c2, c5 = calc(a)
    d[(c2, c5)] += 1
ans = 0
key = list(d.keys())
for i in range(len(key)):
    c2, c5 = key[i]
    v = d[(c2, c5)]
    if (c2 >= 0) & (c5 >= 0):
        ans += v * (v - 1) // 2
    for j in range(i + 1, len(key)):
        n2, n5 = key[j]
        if ((n2 + c2) >= 0) & ((n5 + c5) >= 0):
            ans += v * d[(n2, n5)]
print(ans)

Submission status: Accepted

Solution code:
def count_2_5(a):
  c2 = c5 = 0
  while a % 2 == 0:
    c2 += 1
    a //= 2
  while a % 5 == 0:
    c5 += 1
    a //= 5
  return c2, c5

N = int(input())

# [-9, -8, ..., -1, 0, 1, ..., 8, 9]
base = 9
MAP = [[0]*19 for i in range(19)]
A = []
for i in range(N):
  a = input()
  if '.' in a:
    a, b = a.split('.')
    if int(b):
      c2, c5 = count_2_5(int(a+b))
      c2 -= len(b); c5 -= len(b)
    else:
      c2, c5 = count_2_5(int(a))
  else:
    c2, c5 = count_2_5(int(a))
  
  c2 = min(c2, 9); c5 = min(c5, 9)
  A.append((c2, c5))
  c2 += base; c5 += base
  MAP[c2][c5] += 1

def get_map(i, j):
  try:
    return MAP[i][j]
  except:
    return 0

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

ans = 0
for c2, c5 in A:
  ans += get_map(base-c2, base-c5)
  if c2 >= 0 and c5 >= 0:
    ans -= 1

print(ans//2)

Submission status: Accepted

Solution code:
# import collections

N=int(input())
A=[]
PRECISION_DIGITS=9
cnt={} #collections.defaultdict(int)


for n in range(N):
	tmpA = float(input())
	tmpA = round(tmpA*10**PRECISION_DIGITS)
	#print(tmpA)

	five = 0
	two = 0
	while (tmpA % 2) == 0:
		two += 1
		tmpA //= 2
	while (tmpA % 5) == 0:
		five += 1
		tmpA //= 5

	# (10**9) -> (two,five)=(9,9)
	two -= PRECISION_DIGITS
	five -= PRECISION_DIGITS

	cnt.setdefault((two,five),0)
	cnt[(two,five)]+=1

# print(cnt)
ans = 0
for t1, cnt1 in cnt.items():
	for t2, cnt2 in cnt.items():
		# 2**a(a>=0) and 5**b(b>=0) => integer
		if 0 <= t1[0]+t2[0] and 0 <= t1[1]+t2[1]:
			if t1 < t2:
				ans += int(cnt1*cnt2)
			elif t1 == t2:
				# same entry
				# Total number of combinations choose 2 items
				# nC2 = n*(n-1)/2
				ans += int((cnt1*(cnt2-1))/2)


print(ans)

Submission status: Accepted

Solution code:
import collections

N=int(input())
A=[]
PRECISION_DIGITS=9
cnt=collections.defaultdict(int)


for n in range(N):
	tmpA = float(input())
	tmpA = round(tmpA*10**PRECISION_DIGITS)
	#print(tmpA)

	five = 0
	two = 0
	while (tmpA % 2) == 0:
		two += 1
		tmpA //= 2
	while (tmpA % 5) == 0:
		five += 1
		tmpA //= 5

	# (10**9) -> (two,five)=(9,9)
	two -= PRECISION_DIGITS
	five -= PRECISION_DIGITS

	cnt[(two,five)]+=1

# print(cnt)
ans = 0
for t1, cnt1 in cnt.items():
	for t2, cnt2 in cnt.items():
		# 2**a(a>=0) and 5**b(b>=0) => integer
		if 0 <= t1[0]+t2[0] and 0 <= t1[1]+t2[1]:
			if t1 < t2:
				ans += int(cnt1*cnt2)
			elif t1 == t2:
				# same entry
				# Total number of combinations choose 2 items
				# nC2 = n*(n-1)/2
				ans += int((cnt1*(cnt2-1))/2)


print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N=int(input())
A=[]
PRECISION_DIGITS=9
NO_ENTRY = 0
ARR_SIZE=PRECISION_DIGITS*2+1
cnt=np.full((ARR_SIZE,ARR_SIZE),NO_ENTRY,int)
# cnt=np.zeros((PRECISION_DIGITS*2,PRECISION_DIGITS*2),int)

# print(cnt)

for n in range(N):
	tmpA = float(input())
	tmpA = round(tmpA*10**PRECISION_DIGITS)
	#print(tmpA)

	five = 0
	two = 0
	# (10**9) -> (two,five)=(9,9)
	# min = 10**-9, ignore < 10**9 ???
	while (tmpA % 2) == 0 and two < PRECISION_DIGITS*2:
		two += 1
		tmpA //= 2
	while (tmpA % 5) == 0 and five < PRECISION_DIGITS*2:
		five += 1
		tmpA //= 5

	if cnt[two][five] == NO_ENTRY:
		cnt[two][five]=1
	else:
		cnt[two][five]+=1

# print(cnt)
ans = 0

for x1 in range(ARR_SIZE):
	for y1 in range(ARR_SIZE):
		if cnt[x1][y1] == NO_ENTRY:
			continue

		for x2 in range(x1,ARR_SIZE):
			for y2 in range(ARR_SIZE):
				if cnt[x2][y2] == NO_ENTRY:
					continue
				# 2**a(a>=0) and 5**b(b>=0) => integer
				if 0 <= x1+x2 - PRECISION_DIGITS*2 and 0 <= y1+y2 -PRECISION_DIGITS*2:
					if x1 == x2 and y1 == y2:
						# same entry
						# Total number of combinations choose 2 items
						# nC2 = n*(n-1)/2
						ans += int((cnt[x1][y1]*(cnt[x2][y2]-1))//2)
					else:
						ans += int(cnt[x1][y1]*cnt[x2][y2])

		# completed counted up entry
		cnt[x1][y1] = NO_ENTRY

print(ans)