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:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 998244353


def resolve():
    n = int(input())
    A = []
    for _ in range(n):
        a = float(input())
        a = round(a * 10 ** 9 + 0.1)
        A.append(a)

    L = [[0] * 25 for _ in range(45)]
    D = []
    for a in A:
        tmp = a
        ex2 = ex5 = 0
        while tmp % 2 == 0:
            tmp //= 2
            ex2 += 1
        tmp = a
        while tmp % 5 == 0:
            tmp //= 5
            ex5 += 1
        L[ex2][ex5] += 1
        D.append((ex2, ex5))

    res = 0
    check = [[False] * 25 for _ in range(45)]
    for i in range(45):
        for j in range(25):
            if L[i][j] == 0:
                check[i][j] = True
                continue
            for k in range(18 - i, 45):
                for l in range(18 - j, 25):
                    if check[k][l]:
                        continue
                    if k == i and l == j:
                        res += L[i][j] * (L[k][l] - 1) // 2
                    else:
                        res += L[i][j] * L[k][l]
            check[i][j] = True
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():

    N = int(input())
    d = [[0] * 19 for _ in range(19)]
    c = []
    for _ in range(N):
        x = round(float(input()) * 10**9)
        d2 = 0
        d5 = 0
        while x % 2 == 0 and d2 < 18:
            x //= 2
            d2 += 1
        while x % 5 == 0 and d5 < 18:
            x //= 5
            d5 += 1
        d[d2][d5] += 1

    a = [[0] * 19 for _ in range(19)]
    for i in range(18,-1,-1):
        s = 0
        for j in range(18,-1,-1):
            s += d[i][j]
            a[i][j] = s
            if i < 18:
                a[i][j] += a[i+1][j]

    ans = 0
    for i in range(19):
        for j in range(19):
            ans += d[i][j] * a[18-i][18-j]
            if i >= 9 and j >=9:
                ans -= d[i][j]


    print(ans//2)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

N = int(input())
tf = []

for _ in range(N):
    A = input()[:-1]
    
    if '.' in A:
        i = A.index('.')
        p = len(A)-i-1
        A = int(A[:i]+A[i+1:])
    else:
        p = 0
        A = int(A)
    
    t, f = 0, 0
    
    while A%2==0:
        A //= 2
        t += 1
    
    while A%5==0:
        A //= 5
        f += 1
    
    tf.append((t-p, f-p))

tf.sort(key=lambda x: x[0])
r_idx = N-1
cnt = defaultdict(int)
ans = 0

for t, f in tf:
    while r_idx>=0 and t+tf[r_idx][0]>=0:
        cnt[tf[r_idx][1]] += 1
        r_idx -= 1
    
    for k, v in cnt.items():
        if f+k>=0:
            ans += v
    
    if 2*t>=0 and 2*f>=0:
        ans -= 1

print(ans//2)

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())
counts = [[0 for j in range(19)] for i in range(19)]

for _ in range(N):
    a = float(input())
    a = int(round(a*10**9))

    i, j = 0, 0
    while a % 2 == 0:
        i += 1
        a //= 2
    while a % 5 == 0:
        j += 1
        a //= 5

    i = min(i, 18)
    j = min(j, 18)
    counts[i][j] += 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:
                    ans += counts[i][j]*counts[k][l]

for i in range(9, 19):
    for j in range(9, 19):
        ans -= counts[i][j]

print(ans//2)

Submission status: Accepted

Solution code:
n=int(input())
dp=[[0]*19 for _ in range(19)]
ans=0
for _ in range(n):
  a=round(float(input())*10**9)
  f,t=0,0
  while a%2==0:
    t+=1
    a//=2
  while a%5==0:
    f+=1
    a//=5
  t,f=min(t,18),min(f,18)
  ans+=dp[18-t][18-f]
  for i in range(t+1):
    for j in range(f+1):
      dp[i][j]+=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
dp = [[0]*(19) for _ in range(19)]
ans = 0
for _ in range(N):
    a = round(float(input())*10**9)
    two = 0
    five = 0
    while a%2 == 0:
        a //= 2
        two += 1
    while a%5 == 0:
        a //= 5
        five += 1
    two = min(two,18)
    five = min(five,18)
    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:
import sys
import math
import collections
import bisect
import itertools
import decimal

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
# MOD = 10 ** 9 + 7
MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===
def prime_factorize(n):
    two = 0
    five = 0
    while n % 2 == 0:
        two += 1
        n //= 2

    while n % 5 == 0:
        five += 1
        n //= 5

    return two, five


def main():
    n = ni()
    a = [int(decimal.Decimal(sys.stdin.readline().rstrip()) * (10 ** 9)) for _ in range(n)]
    res = {}
    border = 18

    twoflg = False
    fiveflg = False
    for ai in a:
        two, five = prime_factorize(ai)

        if two >= 9:
            twoflg = True
        if five >= 9:
            fiveflg = True

        if (two, five) not in res.keys():
            res[(two, five)] = 1
        else:
            res[(two, five)] += 1

    ans = 0
    if twoflg and fiveflg:
        for k, v in res.items():
            two, five = k
            for tk, tv in res.items():
                t_two, t_five = tk
                if two + t_two >= border and five + t_five >= border:
                    if two == t_two and five == t_five:
                        ans += v * (tv - 1)
                    else:
                        ans += v * tv

    print(ans // 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import itertools
import decimal

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
# MOD = 10 ** 9 + 7
MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===
def prime_factorize(n):
    two = 0
    five = 0
    while n % 2 == 0:
        two += 1
        n //= 2

    while n % 5 == 0:
        five += 1
        n //= 5

    return two, five


def main():
    n = ni()
    a = [int(decimal.Decimal(input()) * (10 ** 9)) for _ in range(n)]
    res = {}
    border = 18

    twoflg = False
    fiveflg = False
    for ai in a:
        two, five = prime_factorize(ai)

        if two >= 9:
            twoflg = True
        if five >= 9:
            fiveflg = True

        if (two, five) not in res.keys():
            res[(two, five)] = 1
        else:
            res[(two, five)] += 1

    ans = 0
    if twoflg and fiveflg:
        for k, v in res.items():
            two, five = k
            for tk, tv in res.items():
                t_two, t_five = tk
                if two + t_two >= border and five + t_five >= border:
                    if two == t_two and five == t_five:
                        ans += v * (tv - 1)
                    else:
                        ans += v * tv

    print(ans // 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
from decimal import Decimal

def func(n):
    cnt2 = 0
    cnt5 = 0
    while n % 2 == 0:
        n //= 2
        cnt2 += 1
    while n % 5 == 0:
        n //= 5
        cnt5 += 1
    return cnt2, cnt5

def main():
    N = int(input())
    A = [input() for _ in range(N)]
    ctr = Counter()

    for a in A:
        d = Decimal(a)
        d = int(d * 1000000000)
        cnt2, cnt5 = func(d)
        ctr[(cnt2,cnt5)] += 1
    ans = 0
    for (ni1, go1), v1 in ctr.items():
        for (ni2, go2), v2 in ctr.items():
            if not (ni1 + ni2 >= 18 and go1 + go2 >= 18):
                continue
            if ni1 == ni2 and go1 == go2:
                ans += v1 * (v1 - 1)
            else:
                ans += v1 * v2


    print(ans // 2)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter
from decimal import Decimal

def func(n):
    cnt2 = 0
    cnt5 = 0
    while n % 2 == 0:
        n //= 2
        cnt2 += 1
    while n % 5 == 0:
        n //= 5
        cnt5 += 1
    return cnt2, cnt5

def main():
    N = int(input())
    A = [input() for _ in range(N)]
    ctr = Counter()

    for a in A:
        d = Decimal(a)
        d = int(d * 1000000000)
        cnt2, cnt5 = func(d)
        ctr[(cnt2,cnt5)] += 1
    ans = 0
    for (ni1, go1), v1 in ctr.items():
        for (ni2, go2), v2 in ctr.items():
            if not (ni1 + ni2 >= 18 and go1 + go2 >= 18):
                continue
            if ni1 == ni2 and go1 == go2:
                ans += v1 * (v1 - 1)
            else:
                ans += v1 * v2


    print(ans // 2)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

n = int(input())
dp = [[0]*19 for _ in range(19)]
dq = [[0]*19 for _ in range(19)]

for i in range(n):
    s = input()
    x = s.find('.')
    if x == -1:
        s = s + '0'*9
    else:
        s = s.replace('.','') + '0'*(10-(len(s)-x))
    s = int(s)
    d2 = 0
    d5 = 0
    for _ in range(18):
        if s%2 != 0:
            break
        s = s//2
        d2 += 1
    for _ in range(18):
        if s%5 != 0:
            break
        s = s//5
        d5 += 1
    dp[d2][d5] += 1
    dq[d2][d5] += 1

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

ret = 0
for i in range(19):
    for j in range(19):
        if dq[i][j] == 0:
            continue
        ret += dq[i][j] * dp[18-i][18-j]
ret -= dp[9][9]
print(ret//2)

Submission status: Accepted

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

N = int(readline())

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

for i in range(N):
  a = readline().rstrip()
  if "." in a:
    keta = len(a.split(".")[1])
    a = int(a.replace(".","")) * (10 ** (9 - keta))
  else:
    a = int(a) * (10 ** 9)
  cnt2 = 0
  cnt5 = 0
  while a % 2 == 0:
    a //= 2
    cnt2 += 1
  while a % 5 == 0:
    a //= 5
    cnt5 += 1
  C[min(cnt2, 18)][min(cnt5, 18)] += 1

#for c in C:
#  print(c)

ans = 0
# まず、同じグループから2つの数を選ぶ場合の数
for i in range(9, 19):
  for j in range(9, 19):
    n = C[i][j]
    ans += (n * (n - 1)) // 2

# 異なるグループから選ぶ場合の数
ans_diff = 0
for i in range(19):
  for j in range(19):
    for p in range(19):
      for q in range(19):
        if i == p and j == q:
          continue # カウント済
        if i + p < 18 or j + q < 18:
          continue
        ans_diff += C[i][j] * C[p][q]

ans += ans_diff // 2 # 二回カウントしている

print(ans)

Submission status: Accepted

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

N = int(readline())

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

for i in range(N):
  a = readline().rstrip()
  if "." in a:
    keta = len(a.split(".")[1])
    a = int(a.replace(".","")) * (10 ** (9 - keta))
  else:
    a = int(a) * (10 ** 9)
  temp = a
  cnt2 = 0
  cnt5 = 0
  while a % 2 == 0:
    a //= 2
    cnt2 += 1
  while a % 5 == 0:
    a //= 5
    cnt5 += 1
  C[min(cnt2, 18)][min(cnt5, 18)] += 1

#for c in C:
#  print(c)

ans = 0
# まず、同じグループから2つの数を選ぶ場合の数
for i in range(9, 19):
  for j in range(9, 19):
    n = C[i][j]
    ans += (n * (n - 1)) // 2

# 異なるグループから選ぶ場合の数
ans_diff = 0
for i in range(19):
  for j in range(19):
    for p in range(19):
      for q in range(19):
        if i == p and j == q:
          continue # カウント済
        if i + p < 18 or j + q < 18:
          continue
        ans_diff += C[i][j] * C[p][q]

ans += ans_diff // 2 # 二回カウントしている

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [[0]*37 for _ in range(37)]
b = 0
for _ in range(n):
    A = round(float(input())*10**9)
    for i in range(37):
        if A%2 == 0:
            A //= 2
        else:
            x = i
            break
    for i in range(37):
        if A%5 == 0:
            A //= 5
        else:
            y = i
            break
    a[x][y] += 1
for i in range(37):
    for j in range(37):
        for k in range(i+1, 37):
            for l in range(37):
                if i+k >= 18 and j+l >= 18:
                    b += a[i][j]*a[k][l]
for i in range(37):
    for j in range(37):
        for k in range(j, 37):
            if j == k and i >= 9 and j >= 9:
                b += a[i][j]*(a[i][j]-1)//2
            elif j != k and i >= 9 and j+k >= 18:
                b += a[i][j]*a[i][k]
print(b)

Submission status: Accepted

Solution code:
"""
小数の状態だと処理しづらいので、与えられた数を全て10**9倍して小数を確実になくした上で
問題文を下記のように言い換える。
「積が10**18の倍数になるような数の組み合わせの数がいくつあるか」
数Aiがあり、Aiの2の素因数の数がn, 5の素因数の数がmのとき、
数Ai自体ですでにmin(n,m)個の0の数を持っている。この場合、のこり必要な0の数はx = 18-min(n,m)個である。
ここで、n == mの場合：
Aiの相方は少なくとも2,5の素因数をそれぞれx個以上持っていなくてはならない。
n > mの場合：
Aiの相方は少なくとも2の素因数をx-(n-m)個、5の素因数をx個持っていなくてはいけない。

m > nの場合：
Aiの相方は少なくとも2の素因数をx個以上、5の素因数をx-(m-n)個以上持っていなくてはならない。
"""
N = int(input())
dp = [[0]*(19) for _ in range(19)]
ans = 0
for _ in range(N):
    a = round(float(input())*pow(10,9))
    two = 0
    while a % 2 == 0 and two < 18:
        a //= 2
        two += 1
    five = 0
    while a % 5 == 0 and five < 18:
        a //= 5
        five += 1

    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:
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)]
#dp[i][j] -> 2の素因数がi以上,5の素因数がj以上の数字の数

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:
import sys
input = sys.stdin.readline

n = int(input())
ans = 0
cnt = [[0]*20 for _ in range(45)]
for _ in range(n):
    a = list(map(str, input().rstrip().split(".")))
    x = 0
    if len(a) == 1:
        x = int(a[0]) * 10**9
    else:
        x = int(a[0]) * 10**9 + int(a[1]) * pow(10, 9-len(a[1]))
    cnt_2, cnt_5 = 0, 0
    while x % 2 == 0:
        cnt_2 += 1
        x //= 2
    while x % 5 == 0:
        cnt_5 += 1
        x //= 5
    for i in range(45):
        for j in range(20):
            if cnt_2 + i >= 18 and cnt_5 + j >= 18:
                ans += cnt[i][j]
    cnt[cnt_2][cnt_5] += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
class Bit:
    def __init__(self, lst):
        t = 1
        while (t << 1) <= len(lst):
            for i in range(t, len(lst) - t + 1, t << 1):
                lst[i + t - 1] += lst[i - 1]
            t <<= 1
        self.lst = lst

    def add(self, pos, value):
        pos += 1
        while pos <= len(self.lst):
            self.lst[pos - 1] += value
            pos += pos & (-pos)

    def update(self, pos, value):
        diff = value - self.at(pos)
        self.add(pos, diff)

    def at(self, pos):
        return self.sum(pos + 1) - self.sum(pos)
    
    def sum(self, pos):
        # sum of [0, pos)
        if pos == 0:
            return 0
        s = 0
        while pos > 0:
            s += self.lst[pos - 1]
            #pos -= pos & (-pos)
            pos &= ~(-pos)
        return s
    
def solve():
    N = int(readline())
    A = [float(readline()) for i in range(N)]

    C = [0] * N
    c5s = set()

    for i, a in enumerate(A):
        #b = int(a * (10 ** 9))
        #b = a * (10 ** 9)
        b = round(a * (10 ** 9))
        c2, c5 = -9, -9
        while b % 2 == 0:
            b //= 2
            c2 += 1
        while b % 5 == 0:
            b //= 5
            c5 += 1
        
        C[i] = (c2, c5)
    
    Q = [(-a, -b) for a,b in C]

    count0 = sum(a >= 0 and b >= 0 for a,b in C)

    # Coordinate compression
    s1 = set()
    s2 = set()
    for a,b in C:
        s1.add(a)
        s2.add(b)
    for a,b in Q:
        s1.add(a)
        s2.add(b)
    xs = sorted(s1)
    ys = sorted(s2)
    compA = {v: i for i, v in enumerate(xs)}
    compB = {v: i for i, v in enumerate(ys)}
    C = [(compA[a], compB[b]) for a,b in C]
    Q = [(compA[a], compB[b]) for a,b in Q]
    H, W = len(xs), len(ys)

    C.sort()
    Q.sort(reverse=True)

    bit = Bit([0] * W)
    ans = 0

    j = N - 1
    for x, y in Q:
        while j >= 0 and C[j][0] >= x:
            bit.add(C[j][1], 1)
            j -= 1
        ans += bit.sum(W) - bit.sum(y)

    print((ans - count0) // 2)


solve()

Submission status: Accepted

Solution code:
import sys
from itertools import chain

readline = sys.stdin.readline
class Bit:
    def __init__(self, lst):
        t = 1
        while (t << 1) <= len(lst):
            for i in range(t, len(lst) - t + 1, t << 1):
                lst[i + t - 1] += lst[i - 1]
            t <<= 1
        self.lst = lst

    def add(self, pos, value):
        pos += 1
        while pos <= len(self.lst):
            self.lst[pos - 1] += value
            pos += pos & (-pos)

    def update(self, pos, value):
        diff = value - self.at(pos)
        self.add(pos, diff)

    def at(self, pos):
        return self.sum(pos + 1) - self.sum(pos)
    
    def sum(self, pos):
        # sum of [0, pos)
        if pos == 0:
            return 0
        s = 0
        while pos > 0:
            s += self.lst[pos - 1]
            #pos -= pos & (-pos)
            pos &= ~(-pos)
        return s
    
def solve():
    N = int(readline())
    A = [float(readline()) for i in range(N)]

    C = [0] * N
    c5s = set()

    for i, a in enumerate(A):
        #b = int(a * (10 ** 9))
        #b = a * (10 ** 9)
        b = round(a * (10 ** 9))
        c2, c5 = -9, -9
        while b % 2 == 0:
            b //= 2
            c2 += 1
        while b % 5 == 0:
            b //= 5
            c5 += 1
        
        C[i] = (c2, c5)
    
    Q = [(-a, -b) for a,b in C]

    count0 = sum(a >= 0 and b >= 0 for a,b in C)

    # Coordinate compression
    xs = sorted(set(chain((a for a,b in C), (a for a,b in Q))))
    ys = sorted(set(chain((b for a,b in C), (b for a,b in Q))))
    compA = {v: i for i, v in enumerate(xs)}
    compB = {v: i for i, v in enumerate(ys)}
    C = [(compA[a], compB[b]) for a,b in C]
    Q = [(compA[a], compB[b]) for a,b in Q]
    H, W = len(xs), len(ys)

    C.sort()
    Q.sort(reverse=True)

    bit = Bit([0] * W)
    ans = 0

    j = N - 1
    for x, y in Q:
        while j >= 0 and C[j][0] >= x:
            bit.add(C[j][1], 1)
            j -= 1
        ans += bit.sum(W) - bit.sum(y)

    print((ans - count0) // 2)


solve()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
class Bit:
    def __init__(self, lst):
        t = 1
        while (t << 1) <= len(lst):
            for i in range(t, len(lst) - t + 1, t << 1):
                lst[i + t - 1] += lst[i - 1]
            t <<= 1
        self.lst = lst

    def add(self, pos, value):
        pos += 1
        while pos <= len(self.lst):
            self.lst[pos - 1] += value
            pos += pos & (-pos)

    def update(self, pos, value):
        diff = value - self.at(pos)
        self.add(pos, diff)

    def at(self, pos):
        return self.sum(pos + 1) - self.sum(pos)
    
    def sum(self, pos):
        # sum of [0, pos)
        if pos == 0:
            return 0
        s = 0
        while pos > 0:
            s += self.lst[pos - 1]
            #pos -= pos & (-pos)
            pos &= ~(-pos)
        return s
    
def solve():
    N = int(readline())
    A = [float(readline()) for i in range(N)]

    C = [0] * N
    c5s = set()

    for i, a in enumerate(A):
        b = round(a * (10 ** 9))
        c2, c5 = -9, -9
        while b % 2 == 0:
            b //= 2
            c2 += 1
        
        while b % 5 == 0:
            b //= 5
            c5 += 1
        
        C[i] = (c2, c5)
        c5s.add(c5)
        c5s.add(-c5)

    c5_to_i = {c5: i for i, c5 in enumerate(sorted(c5s))}
    
    C.sort()

    c5_comp = [c5_to_i[c5] for c2, c5 in C]
    
    bit = Bit([0] * len(c5_to_i))

    c5_max = max(c5 for c2, c5 in C)


    ans = 0
    j = N - 1
    for i, (c2, c5) in enumerate(C):
        if c2 < 0:
            l, r = i, N
            while l + 1 < r:
                m = (l + r) // 2
                if C[m][0] + c2 >= 0:
                    r = m
                else:
                    l = m
            if r == N:
                continue
            
            while j >= r:
                bit.add(c5_comp[j], 1)
                j -= 1
            
            ans += bit.sum(c5_to_i[c5_max] + 1) - bit.sum(c5_to_i[-c5])
        else:
            while j < i:
                j += 1
                bit.add(c5_comp[j], -1)
            
            while j > i:
                bit.add(c5_comp[j], 1)
                j -= 1

            ans += bit.sum(c5_to_i[c5_max] + 1) - bit.sum(c5_to_i[-c5])
    
    print(ans)


solve()

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())

A = []
for i in range(N):
    num = float(input()) * 10 ** 9 + 0.5
    A.append(int(num))


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


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


table = {}
for i in range(19):
    for j in range(19):
        table[i, j] = 0

for a in A:
    c2 = count2(a)
    c5 = count5(a)
    if(c2 > 18):
        c2 = 18
    if(c5 > 18):
        c5 = 18
    table[c2, c5] += 1

res = 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:
                        res += table[i, j] * (table[i, j] - 1)
                    else:
                        res += table[i, j] * table[k, l]

print(res // 2)

Submission status: Accepted

Solution code:
import decimal
class Imos_2:
    def __init__(self,W,H):
        self.width=W
        self.height=H
        self.list=[[0]*(W+1) for _ in range(H+1)]

    def Add(self,F,T,C=1):
        Fx,Fy=F
        Tx,Ty=T

        self.list[Fx][Fy]+=C
        self.list[Fx][Ty+1]-=C
        self.list[Tx+1][Fy]-=C
        self.list[Tx+1][Ty+1]+=C

    def Cumulative_Sum(self):
        Y=[[0]*(self.height+1) for _ in range(self.width+1)]

        for x in range(self.width+1):
            S=0
            for y in range(self.height+1):
                S+=self.list[x][y]
                Y[x][y]=S

        for y in range(self.height+1):
            S=0
            for x in range(self.width+1):
                S+=Y[x][y]
                Y[x][y]=S

        return Y
#================================================
def f(N):
    R=[]
    for k in [2,5]:
        X=N
        Y=0
        while X%k==0:
            X//=k
            Y+=1
        R.append(min(Y,2*Max_power))
    return R

N=int(input())
Max_power=9
A=[0]*N
I=Imos_2(2*Max_power+1,2*Max_power+1)
Power=[0]*N

for i in range(N):
    A[i]=int(decimal.Decimal(input())*(10**Max_power))

for i in range(N):
    (p,q)=f(A[i])
    Power[i]=(p,q)
    I.Add((2*Max_power-p,2*Max_power-q),(2*Max_power,2*Max_power))

J=I.Cumulative_Sum()

Ans=0
for i in range(N):
    p,q=Power[i]
    Y=J[p][q]

    if (p>=Max_power) and (q>=Max_power):
        Y-=1

    Ans+=Y

print(Ans//2)

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import gcd
nums = defaultdict(int)
for _ in range(int(input())):
  nums[gcd(round(float(input())*(10**9)),10**18)] += 1
nums = tuple(nums.items())
ans = 0
for i, (a,b) in enumerate(nums):
  if a*a%(10**18) == 0:
    ans += b*(b-1)//2
  for (c,d) in nums[i+1:]:
    if a*c%(10**18) == 0:
      ans += b*d
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
b = 10**9
A = [int(round(float(input())*b)) for i in range(N)]
dic = defaultdict(int)
for a in A:
    c2, c5 = 0, 0
    while a % 2 == 0 and c2 < 18:
        c2 += 1
        a //= 2
    while a % 5 == 0 and c5 < 18: 
        c5 += 1
        a //= 5
    dic[(c2, c5)] += 1
ans = 0
for i in range(50):
    for j in range(25):
        for k in range(50):
            for l in range(25):
                if i+k >= 18 and j+l >= 18:
                    if i == k and j == l:
                        ans += dic[(i, j)] * (dic[(i, j)] - 1)
                    else:
                        ans += dic[(i, j)] * dic[(k, l)]
print(ans//2)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
b = 10**9
A = [int(round(float(input())*b)) for i in range(N)]
dic = defaultdict(int)
for a in A:
    c2, c5 = 0, 0
    while a % 2 == 0:
        c2 += 1
        a //= 2
    while a % 5 == 0:
        c5 += 1
        a //= 5
    dic[(c2, c5)] += 1
ans = 0
for i in range(50):
    for j in range(25):
        for k in range(50):
            for l in range(25):
                if i+k >= 18 and j+l >= 18:
                    if i == k and j == l:
                        ans += dic[(i, j)] * (dic[(i, j)] - 1)
                    else:
                        ans += dic[(i, j)] * dic[(k, l)]
print(ans//2)

Submission status: Accepted

Solution code:
from collections import defaultdict

def Com(n, k):
    p, q = 1, 1
    for i in range(n-k+1, n+1):
        p *= i
    for i in range(2, k+1):
        q *= i
    return p//q

N = int(input())
b = 10**9
A = [int(round(float(input())*b)) for i in range(N)]
dic = defaultdict(int)
for a in A:
    c2, c5 = 0, 0
    while a % 2 == 0:
        c2 += 1
        a //= 2
    while a % 5 == 0:
        c5 += 1
        a //= 5
    dic[(c2, c5)] += 1
ans = 0
for i in range(50):
    for j in range(25):
        for k in range(i, 50):
            for l in range(25):
                if not (i==k and j>=l) and i+k >= 18 and j+l >= 18:
                    ans += dic[(i, j)] * dic[(k, l)]
for i in range(50):
    for j in range(25):
        if i+i >= 18 and j+j >= 18 and dic[(i, j)] > 1:
            ans += Com(dic[(i, j)], 2)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

def parse(s):
    if '.' not in s:
        return int(s)*10**9
    else:
        n = len(s)-s.find('.')
        s = s[:-n]+s[-n+1:]+(10-n)*'0'
        return  int(s)

A = [parse(input()) for _ in range(N)]
count = []
for i in range(N):
    n2 = 0
    n5 = 0
    n = A[i]
    while True:
        if n%2==0:
            n2 += 1
            n//=2
        else:
            break
    while True:
        if n%5==0:
            n5 += 1
            n//=5
        else:
            break
    n2 = min(n2,18)
    n5 = min(n5,18)
    count.append((n2,n5))

d = {}
for i in range(19):
    for j in range(19):
        d[(i,j)] = 0
for i in range(N):
    d[count[i]] += 1

dsum = {}
for i in range(19):
    for j in range(19):
        dsum[(i,j)] = 0
        for k in range(18-i,19):
            for l in range(18-j,19):
                dsum[(i,j)] += d[(k,l)]

ans = 0
for i in range(N):
    ans += dsum[count[i]]
    if count[i][0]>=9 and count[i][1]>=9:
        ans -= 1
ans //= 2
print(ans)

Submission status: Accepted

Solution code:
import copy
n = int(input())
def point_shift(s,i):
    p = s.index(".")
    tale = len(s[p+1:])
    if tale <= i:
        return int(s[:p]+s[p+1:].ljust(i,"0"))
    else:
        return int(s[:p]+s[p+1:p+i+1])

a = []
for i in range(n):
    s = input()
    if "." not in s:
        a.append(int(s)*10**9)
    else:
        a.append(point_shift(s,9))

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

l0 = [[0]*100 for _  in range(100)]
for i in range(n):
    l0[memo[i][0]][memo[i][1]] += 1

l1 = copy.deepcopy(l0)
for i in range(100):
    for j in range(98,-1,-1):
        l1[i][j] += l1[i][j+1]
for i in range(98,-1,-1):
    for j in range(100):
        l1[i][j] += l1[i+1][j]


ans = 0
for i in range(100):
    for j in range(100):
        x0,y0 = i,j
        x1,y1 = max(0,18-x0),max(0,18-y0)
        if x0 >= 9 and y0 >= 9:
            ans += l0[x0][y0]*(l1[x1][y1]-1)
        else:
            ans += l0[x0][y0]*l1[x1][y1]
print(ans//2)

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())

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)