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, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

from decimal import Decimal

def gcd(a, b):
	return gcd(b, a%b) if b else a

L = 10**9
LL = 10**18
N = ri()
A = []
for i in range(N):
	d = Decimal(rs())
	A.append(int(d*L))

h = defaultdict(int)
for i in range(N):
	g = gcd(A[i], LL)
	h[g] += 1

ans = 0
for g, c in h.items():
	for g2, c2 in h.items():
		if g == g2:
			if g*g % LL == 0:
				ans += c*(c-1)//2
		elif g < g2:
			if g*g2 % LL == 0:
				ans += c * c2
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [input() for _ in [0]*N]

for i,a in enumerate(A):
    b = a.split(".")
    if len(b)==1:
        A[i] = int(a)*10**9
        continue
    c = b[1]
    n = len(c)
    c += "0"*(9-n)
    A[i] = int(b[0] + c)

cnt = [[0]*40 for _ in [0]*40]
B = [(0,0)]*N
for k,a in enumerate(A):
    i = 0
    j = 0
    while a%2==0:
        a//=2
        i+=1
    while a%5==0:
        a//=5
        j+=1
    B[k] = (i,j)
    cnt[i][j] += 1

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

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

ans = 0
for i,j in B:
    me = int(i>=9 and j>=9)
    ans += cnt[max(0,18-i)][max(0,18-j)]-me

print(ans//2)

Submission status: Accepted

Solution code:
N = int(input())
A = []
C2 = [0] * N
C5 = [0] * N
# for i in range(N):
#     s = str(input())
#     A.append(s)
#     ok = False
#     cnt = 0
#     l = len(A[i])
#     for j in range(l):
#         if A[i][j] == '.':
#             ok = True
#             cnt = j
#     if ok:
#         # 11桁になるまで+0
#         if cnt == 1:
#             while len(A[i]) < 11:
#                 A[i] += "0"
#         # 12
#         elif cnt == 2:
#             while len(A[-1]) < 12:
#                 A[i] += "0"
#     else:
#         A[i] += ".000000000"
#     tmp = ""
#     for j in range(len(A[i])):
#         if A[i][j] == '.':continue
#         tmp += A[i][j]
#     B.append(int(tmp))
P = 1000000000
for i in range(N):
    tmp = input().split(".")
    if len(tmp) == 2:
        a = int(tmp[1])
        for j in range(9-len(tmp[1])):
            a *= 10
        A.append(int(tmp[0]) * P + a)
    else:
        A.append(int(tmp[0]) * P)

for i in range(N):
    tmpp = A[i]
    tmp2 = A[i]
    while tmpp > 0:
        if tmpp % 2 == 0:
            tmpp //= 2
            C2[i] += 1
        else:
            break
    while tmp2 > 0:
        if tmp2 % 5 == 0:
            tmp2 //= 5
            C5[i] += 1
        else:
            break

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

for i in range(N):
    Cc[min(18, C2[i])][min(18, C5[i])]+=1

ans = 0
for i in range(N):
    l2 = max(0, 18 - C2[i])
    l5 = max(0, 18 - C5[i])
    for j in range(l2, 19):
        for k in range(l5, 19):
            ans += Cc[j][k]

for a in A:
    if a % 1000000000 == 0:
        ans -= 1

print(ans//2)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
A = []  # A[i] = A_iが2,5で各々何回割り切れるか
for _ in range(N):
    a = LS2()
    if not '.' in a:
        a = int(''.join(a))
        b,c = 0,0
        while a % 2 == 0:
            a //= 2
            b += 1
        while a % 5 == 0:
            a //= 5
            c += 1
        A.append((b,c))
    else:
        i = a.index('.')
        l = len(a)
        del a[i]
        a += ['0']*(9-l+1+i)
        a = int(''.join(a))  # 与えられた実数を10**9倍したもの
        b,c = 0,0
        while a % 2 == 0:
            a //= 2
            b += 1
        while a % 5 == 0:
            a //= 5
            c += 1
        A.append((b-9,c-9))

from collections import defaultdict
d = defaultdict(int)
for i in range(N):
    d[A[i]] += 1

ans = 0
for a in d.keys():
    b,c = a
    x = 0
    for e in d.keys():
        f,g = e
        if f >= -b and g >= -c:  # 積が整数
            x += d[e]
    ans += d[a]*x

# 自分自身どうしの積が整数となるものを取り除く

for a in d.keys():
    b,c = a
    if b >= 0 and c >= 0:
        ans -= d[a]

print(ans//2)

Submission status: Accepted

Solution code:
from fractions import Fraction
from decimal import Decimal

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

num=[aa.numerator*10**9//aa.denominator for aa in a]

cnt=[[0]*50 for _ in range(50)]
pair=[]

for nu in num:
    c2=0
    c5=0
    while nu>0 and nu%2==0:
        nu//=2
        c2+=1
    
    while nu>0 and nu%5==0:
        nu//=5
        c5+=1
    
    cnt[c2][c5]+=1
    pair.append((c2,c5))
ans=0

for i in range(49,-1,-1):
    for j in range(49,-1,-1):
        if i+1<49:
            cnt[i][j]+=cnt[i+1][j]
        if j+1<49:
            cnt[i][j]+=cnt[i][j+1]

        if i+1<49 and j+1<49:
            cnt[i][j]-=cnt[i+1][j+1]

for c2,c5 in pair:
    ans+=cnt[max(0,18-c2)][max(0,18-c5)]
    if c2>=9 and c5>=9:
        ans-=1

print(ans//2)

Submission status: Accepted

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

N = int(input())
A = [int(10**9*Decimal(input())) for _ in range(N)]

def count(a,p):
  n = a
  count = 0
  while n%p == 0:
    n //= p
    count += 1
  return count

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

print(answer)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline
readline = input

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

from fractions import Fraction

@mt
def slv(N, A):
    c = Counter()
    for a in A:
        a += '.0'
        t = a.split('.')
        b = int(t[0]) * 10**9 + int(t[1]) * 10**(9-len(t[1]))
        n5 = 0
        n2 = 0
        while b % 2 == 0:
            n2 += 1
            b //= 2
        while b % 5 == 0:
            n5 += 1
            b //= 5
        c[(n2, n5)] += 1

    ans = 0
    for k, kk in combinations_with_replacement(c.keys(), r=2):
        if k[0] + kk[0] >= 18 and k[1] + kk[1] >= 18:
            if k == kk:
                ans += c[k] * (c[k]-1) // 2
            else:
                ans += c[k] * c[kk]

    return ans



def main():
    N = read_int()
    A = [input() for _ in range(N)]
    print(slv(N, A))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [input().rstrip() for i in range(n)]
ls0 = []
ls25 = []
for i in range(n):
  s = a[i]
  l = len(s)
  if "." in s:
    pt = s.index(".")
    ls0.append(l-pt-1)
    x = s[:pt]+s[pt+1:]
  else:
    ls0.append(0)
    x = s
  ix = int(x)
  c2 = 0
  while ix%2 == 0:
    c2 += 1
    ix //= 2
  c5 = 0
  ix = int(x)
  while ix%5 == 0:
    c5 += 1
    ix //= 5
  ls25.append((c2-ls0[-1],c5-ls0[-1]))
ls25.sort()
ls2 = list(zip(*ls25))[0]
from collections import defaultdict
import bisect
dic5 = defaultdict(int)
ans = 0
for i in range(n)[::-1]:
  if ls2[i] < 0:
    break
  ind = bisect.bisect_left(ls2,-ls2[i])
  if i == n-1:
    for j in range(ind,n-1):
      dic5[ls25[j][1]] += 1
    ptr = ind
  else:
    for j in range(ptr,ind):
      dic5[ls25[j][1]] -= 1
    dic5[ls25[i][1]] -= 1
    ptr = ind
  for v,num in dic5.items():
    if v+ls25[i][1] >= 0:
      ans += num
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

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

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

N = INT()
K = 10**9
L = 10**18
A = [0] * N
C = Counter()
for i in range(N):
    a = float(input())
    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:
from decimal import *
import sys

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

N = int(input())

A = [Decimal(input()) for i in range(N)]

nanachi = [[0, 0] for i in range(N)]

eprint(A)

def is_integer(n: Decimal):
  return n == n.to_integral_value()

for i, a in enumerate(A):
  t = 0
  while not is_integer(a):
    a *= 10
    t += 1
  nanachi[i][0] = -t
  nanachi[i][1] = -t
  while a % 2 == 0:
    a = a / 2
    nanachi[i][0] += 1
  while a % 5 == 0:
    a = a / 5
    nanachi[i][1] += 1

eprint(nanachi)

tmp = min(map(min, nanachi))

for i in range(N):
  nanachi[i][0] -= tmp
  nanachi[i][1] -= tmp

eprint(nanachi)

aaa = [[0] * 200 for i in range(200)]

for a in nanachi:
  aaa[a[0]][a[1]] += 1

acc = [[0] * 201 for i in range(201)]

for i in reversed(range(0, 200)):
  for k in reversed(range(0, 200)):
    acc[i][k] = acc[i+1][k] + acc[i][k+1] - acc[i+1][k+1] + aaa[i][k]

res = 0

for a in nanachi:
  i = max(0, - (a[0] + 2*tmp))
  k = max(0, - (a[1] + 2*tmp))
  res += acc[i][k]
  if a[0] >= -tmp and a[1] >= -tmp:
    res -= 1

res = res // 2

print(res)

Submission status: Accepted

Solution code:
N = int(input())
A = []

for i in range(N):
    s = input()
    if '.' in s:
        a,b = map(int,s.split('.'))
        if(int(b)==0):
            c = a
            d = 1
        else:
            c = a*pow(10,len(s)-s.find('.')-1)+b
            d = pow(10,len(s)-s.find('.')-1)
    else:
        c = int(s)
        d = 1
    e = 0
    f = 0
    while(c != 0 and c%2==0):
        e += 1
        c //= 2
    while(c != 0 and c%5==0):
        f += 1
        c //= 5
    while(d%2==0):
        e -= 1
        d //=2
    while(d%5==0):
        f -= 1
        d //=5
    A.append([e,f])

tm = max(max([a[0] for a in A]), -1 * min([a[0] for a in A])) + 1
fm = max(max([a[1] for a in A]), -1 * min([a[1] for a in A])) + 1

B = [[0] * (tm * 2 ) for _ in range(fm * 2)]

for a in A:
    B[a[1]+fm][a[0]+tm] += 1

for i in range(fm*2):
    for j in range(tm*2):
        if(i>0):
            B[i][j] += B[i-1][j]
        if(j>0):
            B[i][j] += B[i][j-1]
        if(i>0 and j>0):
            B[i][j] -= B[i-1][j-1]

ans = 0
for a in A:
    i = -1 * a[1] + fm
    j = -1 * a[0] + tm
    ans += B[fm*2-1][tm*2-1] - B[fm*2-1][j-1] - B[i-1][tm*2-1] + B[i-1][j-1]
    if a[1]>=0 and a[0]>=0:
        ans -= 1

print(ans//2)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())

AS = [input().strip() for _ in range(N)]

nums = [int(a.replace('.', '')) for a in AS]
dens = [1 if '.' not in a else 10**(len(a) - a.index('.') - 1) for a in AS]

# print(nums, dens)

def gcd(a, b):
    if a < b:
        return gcd(b, a)
    if b == 0:
        return a
    return gcd(b, a%b)

gs = [gcd(num, den) for num, den in zip(nums, dens)]
nums = [num // g for num, g in zip(nums, gs)]
dens = [den // g for den, g in zip(dens, gs)]

def signature(n):
    e2, e5 = 0, 0
    while n % 2 == 0:
        n //= 2
        e2 += 1
    while n % 5 == 0:
        n //= 5
        e5 += 1
    return (e2, e5)

lookup = defaultdict(int)
for num, den in zip(nums, dens):
    n2, n5 = signature(num)
    d2, d5 = signature(den)
    lookup[(n2-d2, n5-d5)]+=1

ans = 0
for k1 in lookup:
    for k2 in lookup:
        v1, v2 = lookup[k1], lookup[k2]
        x1, y1 = k1
        x2, y2 = k2
        if x1 + x2 >= 0 and y1 + y2 >=0:
            if k1 == k2:
                ans += v1*(v1-1)
            else:
                ans += v1*v2

ans //= 2
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
mod_list = []
for i in range(n):
    a = input()
    dot = a.find('.')
    if dot < 0:
        num = int(a) * 1000000000
    elif dot == len(a) - 1:
        num = int(a[:dot]) * 1000000000
    else:
        rest = len(a) - 1 - dot
        num = int(a[:dot]) * 1000000000 + int(int(a[dot + 1:]) * pow(10, 9 - rest))
    mod2 = mod5 = 0
    while num % 2 == 0:
        num = num / 2
        mod2 += 1
    while num % 5 == 0:
        num = num / 5
        mod5 += 1
    mod_list.append((mod2, mod5))

raw_table = [[0 for j in range(50)] for i in range(50)]
for mod2, mod5 in mod_list:
    raw_table[mod2][mod5] += 1
dp_table = [[0 for j in range(50)] for i in range(50)]
for i in range(48, -1, -1):
    row_sum = raw_table[i][49]
    for j in range(48, -1, -1):
        row_sum += raw_table[i][j]
        dp_table[i][j] = dp_table[i + 1][j] + row_sum

count = 0
for mod2, mod5 in mod_list:
    need2 = max(18 - mod2, 0)
    need5 = max(18 - mod5, 0)
    count += dp_table[need2][need5]
    if need2 <= mod2 and need5 <= mod5:
        count -= 1
print(int(count / 2))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
    res = [None] * n
    for i in range(n):
        res[i] = II()
    return res
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI()
    return res
def FR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
def LIF(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
def SR(n):
    res = [None] * n
    for i in range(n):
        res[i] = S()
    return res
def LSR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LS()
    return res
mod = 1000000007
inf = float('INF')
class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size

    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        i = 0
        s = 0
        step = 1 << self.size.bit_length()
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                print(self.bit[i + step - 1], i, step)
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i

    def __len__(self):
        return self.size
#solve
def solve():
    n = II()
    tmp = []
    ans = 0
    for i in range(n):
        s = S().split(".")
        si = s
        if len(s) == 1:
            s = s[0]
            s = s + "0" * 9
            s = int(s)
        else:
            s0 = s[0]
            s1 = s[1] + "0" * 9
            s = s0 + s1[:9]
            s = int(s)
        t, f = 0, 0
        while s % 2 == 0:
            t += 1
            s //= 2
        while s % 5 == 0:
            f += 1
            s //= 5
        if min(t, f) * 2 >= 18:
            ans -= 1
        tmp.append([t, f, si])
    tmp.sort()
    bitt = BinaryIndexedTree(100)
    r = n - 1
    h = 0
    for i in range(n):
        t, f,_ = tmp[i]
        while r >= 0 and tmp[r][0] + t >= 18:
            bitt.add(tmp[r][1], 1)
            r -= 1
            h += 1
        ans += h - bitt.sum(18 - f - 1)
    print(ans //2)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
class Acc2D:
    def __init__(self, a):
        h, w = len(a), len(a[0])
        self.acc2D = self._build(h, w, a)

    def _build(self, h, w, a):
        ret = [[0] * (w + 1) for _ in range(h + 1)]
        for r in range(h):
            for c in range(w):
                ret[r + 1][c + 1] = ret[r][c + 1] + ret[r + 1][c] - \
                    ret[r][c] + a[r][c]
        return ret

    def get(self, r1, r2, c1, c2):
        # [r1,r2), [c1,c2) : 0-indexed
        acc2D = self.acc2D
        return acc2D[r2][c2] - acc2D[r1][c2] - acc2D[r2][c1] + acc2D[r1][c1]


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())

    G = [[0] * 101 for _ in range(101)]
    # G[p2][p5]

    data = []
    for _ in range(N):

        *a, = input().rstrip().split('.')

        lena = 0
        p2, p5 = 0, 0
        if len(a) > 1:
            a[1] = a[1].rstrip('0')
            lena = len(a[1])
            a[0] = a[0] + a[1]
            p2 = p5 = -lena

        c = int(a[0])
        if c:
            while c % 2 == 0:
                c //= 2
                p2 += 1
            while c % 5 == 0:
                c //= 5
                p5 += 1

        p2 += 40
        p5 += 40
        G[p2][p5] += 1
        data.append((p2, p5))

    acc2d = Acc2D(a=G)

    ans = 0
    for p2, p5 in data:
        ans += acc2d.get(80 - p2, -1, 80 - p5, -1)
        if p2 >= 40 and p5 >= 40:
            ans -= 1
    ans //= 2
    print(ans)


if __name__ == '__main__':
    main()

# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Accepted

Solution code:
import bisect
from heapq import heappush, heappop
n = int(input())
a = []
for i in range(n):
    temp = float(input()) * (10**9)
    a.append(int(temp+0.1))
b = []
d = {0:0,1:0,2:0,3:0,4:0,5:0}
p = [[]for i in range(19)]
for i in a:
    cnt2 = 0
    cnt5 = 0
    while i%2 == 0:
        i //= 2
        cnt2 += 1
    while i%5 == 0:
        i //= 5
        cnt5 += 1
    p[min(18,cnt2)].append(-cnt5)
    # d[min(5,cnt5)] += 1
    # b.append([cnt2,cnt5])
# print(b)
# print(d)
ans = 0
for i in range(19):
    p[i] = sorted(p[i])
# print(p)
for i in range(19):
    while p[i]:
        t = p[i].pop()
        # print(t)
        # for j in p[i]:
        for k in range(max(0,18-i),19):
            # print(k,p[k],t,bisect.bisect_right(p[k],-18-t))
            ans += bisect.bisect_right(p[k],-18-t)
print(ans)
# for i in range(len(a)-1):
#     for j in range(i+1,len(a)):
#         if a[i] > 0 and a[j] > 0 and a[i]*a[j] %(10**8) == 0:
#             ans += 1
#             # print(a[i],a[j])
# print(ans)
# print(a)

Submission status: Accepted

Solution code:
def how(c):
    if float(c).is_integer() == True:
        return int(float(c)),0
    else:
        dot=0
        while c[dot]!=".":
            dot+=1
        c = list(c)
        del c[dot]
        c ="".join(c)
        return int(c),len(c)-dot

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

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

N = int(input())

A = []

for i in range(N):
    A.append(how(input()))


ruiseki = [[0]*120 for i in range(120)]

motoseisuu=0
for i in range(N):
    ruiseki[A[i][1]-lo2(A[i][0])+60][A[i][1]-lo5(A[i][0])+60]+=1
    if A[i][1]==0:
        motoseisuu +=1

for i in range(1,120):
    for j in range(1,120):
        ruiseki[i][j]=ruiseki[i-1][j]+ruiseki[i][j-1]-ruiseki[i-1][j-1]+ruiseki[i][j]


ans = 0
for i in range(N):
    ans+=ruiseki[lo2(A[i][0])+60-A[i][1]][lo5(A[i][0])+60-A[i][1]]

print((ans-motoseisuu)//2)

Submission status: Accepted

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    from collections import defaultdict
    dd = defaultdict(int)
    M=10**10

    
    for _ in range(N):
        c=input()
        if "." in c:
            d=c.index(".")
            a=c[:d]
            b=c[d+1:]
            lb=len(b)
            b+="0"*(10-lb)
        else:
            a=c
            b=0
        c=int(a)*M +int(b)
        
        
        if int(a)==0 and int(b)==0:
            dd[10,10]+=1
        else:
            i=0
            j=0
            while c%2==0:
                c=c//2
                i+=1
            while c%5==0:
                c=c//5
                j+=1
            i-=10
            j-=10
            i=min(i,10)
            j=min(j,10)
            dd[(i,j)]+=1

    ans=0
    
    #dd同士の重複に注意
    
    K=[]
    V=[]
    for k,v in dd.items():
        K.append(k)
        V.append(v)
        
    
    for iiii in range(len(K)):
        k=K[iiii]
        v=V[iiii]
    
        ii,jj=k
        for i in range(-10,11):
            for j in range(-10,11):
                if ii+i>=0 and jj+j>=0:
                    if ii==i and jj==j:
                        temp=dd[(i,j)]
                        ans+=temp*(temp-1)
                    else:
                        ans+=dd[(i,j)]*v
        # print(k,v,ans)
                    
                    
                    
    print(ans//2)
            
    

            
                    
                       

 
               

main()

Submission status: Accepted

Solution code:
from collections import defaultdict


n = int(input())
jisho = defaultdict(int)
for _ in range(n):
    s = input()
    if int(float(s)) == float(s):
        num = int(float(s))
        cnt2 = 0
        cnt5 = 0
    else:
        a, b = s.split(".")
        keta = len(b)
        cnt2 = -keta
        cnt5 = -keta
        a = int(a)
        b = int(b)
        num = a * pow(10, keta) + b
    while True:
        if num % 5 == 0:
            num //= 5
            cnt5 += 1
        else:
            break
    while True:
        if num % 2 == 0:
            num //= 2
            cnt2 += 1
        else:
            break
    if cnt5 <= -11 or cnt2 <= -11:
        continue
    cnt2 = min(10, cnt2)
    cnt5 = min(10, cnt5)
    jisho[(cnt2, cnt5)] += 1
ans = 0
for i in range(21):
    i -= 10
    for j in range(21):
        j -= 10
        kouho1 = jisho[(i, j)]
        if kouho1 == 0:
            continue
        for k in range(21):
            k -= 10
            for l in range(21):
                l -= 10
                kouho2 = jisho[(k, l)]
                if kouho2 == 0:
                    continue

                if i + k >= 0 and j + l >= 0:
                    if (i, j) == (k, l):
                        ans += kouho1 * (kouho2 - 1)
                    else:
                        ans += kouho1 * kouho2

print(ans // 2)

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

n = int(input())
cnt = [[0 for _ in range(20)] for _ in range(20)]
ans = 0
for _ in range(n):
	a = input()
	x, y = 0, 0
	if "." in a:
		i = len(a)-1
		while a[i] != ".":
			i -= 1
			x, y = x-1, y-1
		b = int(a[:i] + a[i+1:])
	else:
		b = int(a)
	#print(b)
	while b%2 == 0 and x < 9:
		x += 1
		b //= 2
	while b%5 == 0 and y < 9:
		y += 1
		b //= 5
	#print(x, y)
	x, y = x+9, y+9
	for i in range(18-x, 20):
		for j in range(18-y, 20):
			ans += cnt[i][j]
	cnt[x][y] += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from decimal import Decimal

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

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

N = INT()
K = 10**9
L = 10**18
A = [0] * N
C = Counter()
for i in range(N):
    a = Decimal(input())
    A[i] = int(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:
n = int(input())
a = [round(float(input()) * 10**9) for _ in range(n)]
cs = [[0] * 20 for _ in range(20)]

dc = []
for i in a:
    x = 0
    for _ in range(18):
        if i % 2 == 0:
            i //= 2
            x += 1
    y = 0
    for _ in range(18):
        if i % 5 == 0:
            i //= 5
            y += 1

    cs[18-x][18-y] += 1
    dc.append((x, y))
for i in range(20):
    for j in range(19):
        cs[i][j+1] += cs[i][j]
for i in range(20):
    for j in range(19):
        cs[j+1][i] += cs[j][i]


ans = 0
for x, y in dc:
    ans += cs[x][y]
for i in a:
    if i % 10**9 == 0:
        ans -= 1
ans //= 2

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
dic = defaultdict(int)
for i in range(N):
    A = int(float(input())*10**9+0.1)
    two = 0
    five = 0
    while A % 2 == 0:
        A //= 2
        two += 1
    while A % 5 == 0:
        A //= 5
        five += 1
    dic[(two,five)] += 1
ans = 0
for T1,F1 in dic.keys():
    for T2,F2 in dic.keys():
        if T1+T2 >= 18 and F1+F2 >= 18:
            X = dic[(T1,F1)]
            Y = dic[(T2,F2)]
            if T1 == T2 and F1 == F2:
                ans += X*(X-1)
            else:
                ans += X*Y
print(ans//2)

Submission status: Accepted

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


N, = map(int, input().split())
M = 51
C2 = [0]*M
C5 = [0]*M
C = [[0]*(M+1) for _ in range(M+1)]
CC = []
for _ in range(N):
    c2, c5 = 9, 9
    s = input().strip()
    if "." in s:
        a, b = s.split(".")
        b.rstrip("0")
        if len(b) != 0:
            c2 -= len(b)
            c5 -= len(b)
        x = int(a + b)
    else:
        x = int(s)
#    print(x, c2, c5)
    while x % 2 == 0:
        x//=2
        c2 += 1
    while x % 5 == 0:
        x//=5
        c5 += 1
    C[c2][c5] += 1
    CC.append((c2, c5))
R = [[0]*(M+1) for _ in range(M+1)]
for i in range(1, M+1):
    for j in range(1, M+1):
        R[i][j] = R[i-1][j] + R[i][j-1] - R[i-1][j-1] + C[i-1][j-1]
r = 0
for a, b in CC:
    if a >= 9 and b >= 9:
        r -= 1
    a, b = max(18-a, 0), max(18-b, 0)
    r += R[M][M] - R[a][M] - R[M][b] + R[a][b]
print(r//2)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for i in range(n):
  s=input()
  if "." in s:
    s+="0"*(9-(len(s)-s.find(".")-1))
    s=s.replace(".","")
  else:s+="0"*9
  s=int(s)
  a.append(int(s))
n=len(a)
tf=[[0]*19 for _ in range(19)]
for x in a:
  two=0
  five=0
  while x%2==0:
    x//=2
    two+=1
  while x%5==0:
    x//=5
    five+=1
  two=min(two,18)
  five=min(five,18)
  tf[two][five]+=1
ans=0
for t1 in range(19):
  for f1 in range(19):
    for t2 in range(19):
      for f2 in range(19):
        if t1+t2<18 or f1+f2<18:continue
        if t1==t2 and f1==f2:
          ans+=tf[t1][f1]*(tf[t1][f1]-1)
        else:
          ans+=tf[t1][f1]*tf[t2][f2]
print(ans//2)