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:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def is_ok(arg):
    return a[i][j]+a[arg][j] >= 0

def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

n = INT()
a = [[0]*19 for i in range(19)]
for i in range(n):
    A = int(float(input())*10**9+0.5)
    m2 = m5 = 0
    while A % 2 == 0:
        A //= 2
        m2 += 1
    while A % 5 == 0:
        A //= 5
        m5 += 1
    m2 = min(m2, 18)
    m5 = min(m5, 18)
    a[m2][m5] += 1

ans = 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:
                        ans += a[i][j] * ( a[k][l] - 1 )
                    else:
                        ans += a[i][j] * a[k][l]
ans //= 2
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

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

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

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = []
dic = DD(int)
for _ in range(N):
  s = S().split(".")
  if len(s) == 1:
    temp = int(s[0])*(10**9)
  else:
    temp = int(s[0])*(10**9)+int(s[1])*(10**(9-len(s[1])))
  _2,_5 = 0,0
  copy = temp
  while copy%2 == 0:
    _2 += 1
    copy //= 2
    if _2 == 18: break
  copy = temp
  while copy%5 == 0:
    _5 += 1
    copy //= 5
    if _5 == 18: break
  dic[(_2,_5)] += 1

ans1 = 0
ans2 = 0
for i2 in range(19):
  for j2 in range(18-i2,19):
    for i5 in range(19):
      for j5 in range(18-i5,19):
        if (i2,i5)==(j2,j5):
          ans1 += dic[(i2,i5)]*(dic[(j2,j5)]-1)
        else:
          ans2 += dic[(i2,i5)]*dic[(j2,j5)]

print((ans1+ans2)//2)

Submission status: Accepted

Solution code:
n=int(input())
cnt=[[0]*19 for _ in range(19)]
for i in range(n):
  a=input()
  i2,i5=0,0
  if '.' in a:
    b,c=a.split('.')
    i2-=len(c)
    i5-=len(c)
    x=int(b+c)
  else:
    x=int(a)
  while x%2==0:
    x//=2
    i2+=1
  while x%5==0:
    x//=5
    i5+=1
  i2=min(i2,9)
  i5=min(i5,9)
  cnt[i2+9][i5+9]+=1

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

for i in range(17,-1,-1):
  csum[i][-1]=cnt[i][-1]+csum[i+1][-1]
  
for j in range(17,-1,-1):
  csum[-1][j]=cnt[-1][j]+csum[-1][j+1]
  
for i in range(17,-1,-1):
  for j in range(17,-1,-1):
    csum[i][j]=csum[i+1][j]+csum[i][j+1]+cnt[i][j]-csum[i+1][j+1]

ans=0
for i in range(19):
  for j in range(19):
    if cnt[i][j]==0:
      continue
    i2=i-9
    i5=j-9
    x=csum[9-i2][9-i5]
    if 9-i2<=i and 9-i5<=j:
      x-=1
    ans+=x*cnt[i][j]
print(ans//2)

Submission status: Accepted

Solution code:
N = int(input())
A = []
for i in range(N):
    s = input().strip().split(".")
    a = int(s[0]) * (10 ** 9)
    if len(s) > 1:
        t = s[1] + "0" * (9 - len(s[1]))
        a += int(t)
    A.append(a)
    
c = [[0 for _ in range(19)] for _ in range(19)]

for i in range(N):
    p = A[i]
    cnt2 = 0
    while(not p % 2):
        p /= 2
        cnt2 += 1

    p = A[i]
    cnt5 = 0
    while(not p % 5):
        p /= 5
        cnt5 += 1
    #print(A[i], cnt2, cnt5)
    c[min(cnt2, 18)][min(cnt5, 18)] += 1
    
ans = 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 and c[i][j]:  ans += (c[i][j] * (c[i][j] - 1))
                    else:  ans += (c[i][j] * c[k][l])
print(ans // 2)

Submission status: Accepted

Solution code:
from decimal import Decimal
N = int(input())
#numlist = [0] * (N + 1)
log2 = [0] * (N + 1)
log5 = [0] * (N + 1)
acc = [[0 for i in range(19)] for j in range(19)]
Ans = 0

for i in range(1,N+1):
  #numlist[i] = Decimal(input()) * 1000000000
  wk = Decimal(input())
  wk = int(wk * 1000000000)

  #wk = numlist[i]
  for cnt in range(1,19):
    if wk % 2 == 0:
      log2[i] += 1
      wk = wk // 2
    else:
      break

  for cnt in range(1,19):
    if wk % 5 == 0:
      log5[i] += 1
      wk = wk // 5
    else:
      break

  acc[log2[i]][log5[i]] += 1
    
for i in range(0,19):
  for j in range(0,19): 
    for k in range(i,19):
      for l in range(0,19):
        if (i + k) >= 18 and (j + l) >= 18 and (i < k or (i == k and j <= l)):
          if acc[i][j] > 0 and acc[k][l] > 0:
            Ans += acc[i][j] * acc[k][l]
            if i >= 9 and j >= 9 and i == k and j == l:
              Ans -= int((acc[i][j] * (acc[i][j] + 1)) / 2)

print(int(Ans))

Submission status: Accepted

Solution code:
from decimal import Decimal
N = int(input())
A = []
for _ in range(N):
    a = Decimal(input())
    A.append(int(a * 10**9))
C = [[0 for j in range(19)] for i in range(44)]
for a in A:
    i = 0
    k = a
    while k % 2 == 0:
        k //= 2
        i += 1
    j = 0
    k = a
    while k % 5 == 0:
        k //= 5
        j += 1
    C[i][j] += 1
res = 0
for i in range(44):
    for j in range(19):
        for ii in range(44):
            for jj in range(19):
                if i + ii >= 18 and j + jj >= 18:
                    res += C[i][j] * C[ii][jj]
for a in A:
    if a**2 % 10**18 == 0:
        res -= 1
res //= 2
print(res)

Submission status: Accepted

Solution code:
import sys

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


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

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

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

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

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

        c[(i, j)] += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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


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


def main():
    N = int(input())
    A = []
    for _ in range(N):
        s = input().strip().split(".")
        a = int(s[0]) * (10 ** 9)
        if len(s) > 1:
            t = s[1] + "0" * (9 - len(s[1]))
            a += int(t)
            # a += int(float("0." + s[1]) * (10 ** 9))
        # a = int(float(input()) * (10 ** 9))
        # print(a)
        A.append(dev(a))
    # print(A)
    S = [[0] * 19 for _ in range(19)]
    dp = [[0] * 20 for _ in range(20)]
    for a in A:
        S[a[2]][a[5]] += 1

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

Submission status: Accepted

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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


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

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

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

print(ans)

Submission status: Accepted

Solution code:
from math import gcd
from collections import Counter

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

# fiveの和とtwoの和が共に18以上ならOK
# 条件を満たすcnts        
ans = 0
for i1 in range(19):
    for j1 in range(19):
        for i2 in range(19):
            for j2 in range(19):
                if i1+i2 >= 18 and j1+j2>=18:
                    ans += cnts[i1][j1]*cnts[i2][j2]

# 自分自身を除外
for i in range(19):
    for j in range(19):
        if i*2 >= 18 and j*2 >= 18:
            ans -= cnts[i][j]

# ダブルカウント
ans //= 2
print(ans)

Submission status: Accepted

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

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

# fiveの和とtwoの和が共に18以上ならOK
# 条件を満たすcnts        
ans = 0
for i1 in range(19):
    for j1 in range(19):
        for i2 in range(19):
            for j2 in range(19):
                if i1+i2 >= 18 and j1+j2>=18:
                    ans += cnts[i1][j1]*cnts[i2][j2]

# 自分自身を除外
for i in range(19):
    for j in range(19):
        if i*2 >= 18 and j*2 >= 18:
            ans -= cnts[i][j]

# ダブルカウント
ans //= 2
print(ans)

Submission status: Accepted

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

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(round(float(input())*10**9))
    p,q = waru(a,2)-9-50,waru(a,5)-9-50
    num[p][q] += 1
    lis[i] = [p,q]
  cum2 = [[0]*101 for _ in range(101)]
  for i in range(99,-1,-1):
    for j in range(99,-1,-1):
      cum2[i][j] = cum2[i+1][j]+cum2[i][j+1]-cum2[i+1][j+1]+num[i][j]
  ans = 0
  for i in range(N):
    p,q = lis[i]
    x,y = p+50,q+50
    p = -x-50
    q = -y-50
    ans += cum2[p][q]
    if x>=0 and y>=0:
      ans -= 1
  return ans//2
print(solve())

Submission status: Accepted

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

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

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

print(int(ans))

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline

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

Submission status: Accepted

Solution code:
# A

from decimal import *

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

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

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

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


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

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

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

import random

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

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

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

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

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

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

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

	print(res//2)


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

if __name__ == "__main__":
	main()

Submission status: Accepted

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

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

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

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

# print(lst)

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

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

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

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

Submission status: Accepted

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

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

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


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

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

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

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

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from decimal import Decimal
import sys
input=sys.stdin.readline

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

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

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

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

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