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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve0(N, AS):
    ret = 0
    for i in range(N):
        for j in range(i + 1, N):
            if AS[i] * AS[j] % 1000000000_000000000 == 0:
                # debug(": AS[i], AS[j]", AS[i], AS[j])
                ret += 1
    return ret


def solve1(N, AS):
    ret = 0
    P2 = []
    P5 = []
    for i in range(N):
        p2 = 0
        p5 = 0
        x = AS[i]
        while x % 2 == 0:
            p2 += 1
            x //= 2
        while x % 5 == 0:
            p5 += 1
            x //= 5
        P2.append(p2)
        P5.append(p5)
    # debug(": P2, P5", P2, P5)
    for i in range(N):
        for j in range(i + 1, N):
            if P2[i] + P2[j] > 17 and P5[i] + P5[j] > 17:
                # debug(": AS[i], AS[j]", AS[i], AS[j])
                ret += 1
    return ret


def solve(N, AS):
    import numpy as np
    ret = 0
    P2 = []
    P5 = []
    P = np.zeros((20, 20), dtype=np.int)

    for i in range(N):
        p2 = 0
        p5 = 0
        x = AS[i]
        while x % 2 == 0:
            p2 += 1
            x //= 2
        while x % 5 == 0:
            p5 += 1
            x //= 5
        if p2 > 18:
            p2 = 18
        P2.append(p2)
        P5.append(p5)
        P[p2, p5] += 1

    for i in range(19, 0, -1):
        P[i - 1] += P[i]
    for i in range(19, 0, -1):
        P[:, i - 1] += P[:, i]

    for i in range(N):
        ret += P[18 - P2[i], 18 - P5[i]]
    ret -= P[9, 9]
    ret //= 2
    return ret


def main():
    # parse input
    N = int(input())
    AS = []
    for i in range(N):
        s = input().strip()
        try:
            v = int(s) * 1000000000
        except:
            s1, s2 = s.split(b".")
            s2 = s2 + b"0" * (9 - len(s2))
            v = int(s1) * 1000000000 + int(s2)
        # print(v)
        AS.append(v)
    print(solve(N, AS))


# tests
T1 = """
5
7.5
2.4
17.000000001
17
16.000000000
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
3
"""

T2 = """
11
0.9
1
1
1.25
2.30000
5
70
0.000000001
9999.999999999
0.999999999
1.000000001
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
8
"""

T3 = """
12
1
5
25
125
625
3125
1.0
0.2
0.04
0.008
0.0016
0.00032
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
36
"""

T4 = """
2
1
1.0
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
1
"""

T5 = """
4
1
5
1.0
0.2
"""
TEST_T5 = """
>>> as_input(T5)
>>> main()
4
"""

T6 = """
6
1
5
25
1.0
0.2
0.04
"""
TEST_T6 = """
>>> as_input(T6)
>>> main()
9
"""

T7 = """
8
1
5
25
125
1.0
0.2
0.04
0.008
"""
TEST_T7 = """
>>> as_input(T7)
>>> main()
16
"""

T8 = """
1
8192
"""
TEST_T8 = """
>>> as_input(T8)
>>> main()
0
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n = int(readline())
#C = [0]*n
#D = [0]*n

"""
dp[i][j] = 2,5で何回割れるか
"""
dp = [[0]*20 for _ in range(50)]

M = 10**9
for i in range(n):
    bi = float(readline())
    ai = int(round(bi*M))
    
    c2=c5=0    
    x = ai
    while x%2==0:
        c2 += 1
        x//=2
    
    x = ai
    while x%5==0:
        c5 += 1
        x//=5
    #C[i] = c2
    #D[i] = c5
    dp[c2][c5] += 1
    #print(c2,c5)

"""
dp[i][j] = 2,5で何回割れるか(50*20)
"""
acc = [dp[i][:] for i in range(50)]
for i in range(49,-1,-1):
    for j in range(19,-1,-1):
        if i != 49:
            acc[i][j] += acc[i+1][j] 
        if j != 19:
            acc[i][j] += acc[i][j+1] 
        if i != 49 and j != 19:
            acc[i][j] -= acc[i+1][j+1] 
            
ans = 0
for i in range(50):
    for j in range(20):
        ans += dp[i][j] * acc[max(0,18-i)][max(0,18-j)]
        if i >= 9 and j >= 9: ans -= dp[i][j]

#print(ans)
print(ans//2)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N = NI()
    A = [SI() for _ in range(N)]
    B = defaultdict(list)
    for a in A:
        if a.count(".") != 1:
            B[int(a)].append(1)
            continue
        ba, bb = a.split(".")
        ba = int(ba+bb)
        bb = 10**len(bb)
        g = math.gcd(ba, bb)
        ba //= g
        bb //= g
        B[ba].append(bb)

    facts = defaultdict(int)
    for ba, bbs in B.items():
        tmp = ba
        ba_fac_2 = 0
        while True:
            if tmp % 2: break
            ba_fac_2 += 1
            tmp //= 2
        tmp = ba
        ba_fac_5 = 0
        while True:
            if tmp % 5: break
            ba_fac_5 += 1
            tmp //= 5

        for bb in bbs:
            tmp = bb
            bb_fac_2 = 0
            while True:
                if tmp % 2: break
                bb_fac_2 += 1
                tmp //= 2
            tmp = bb
            bb_fac_5 = 0
            while True:
                if tmp % 5: break
                bb_fac_5 += 1
                tmp //= 5
            facts[(ba_fac_2 - bb_fac_2, ba_fac_5 - bb_fac_5)] += 1

    ans = 0
    for fact, k in list(facts.items()):

        fac2, fac5 = fact
        for i in range(-fac2, 50):
            for j in range(-fac5, 20):
                if fac2 == i and fac5 == j:
                    ans += k * (k-1)
                else:
                    ans += k * facts[(i, j)]


    print(ans//2)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

import array
from bisect import *
from collections import *
from decimal import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

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


arr = [[0 for _ in range(20)] for _ in range(20)]

cnt = Counter()
N = int(input())
for n in range(N):
    s = input()
    d = Decimal(s)
    d = int(d * 1000000000)
    cnt2, cnt5 = func(d)
    # print(d)
    # print(cnt2, cnt5)
    cnt[(cnt2, cnt5)] += 1

    cnt2 = min(cnt2, 18)
    cnt5 = min(cnt5, 18)
    arr[cnt2][cnt5] += 1

# from pprint import *
# import copy

# sumarr = copy.deepcopy(arr)
# for i in range(18, -1, -1):
#     for j in range(18, -1, -1):
#         sumarr[i][j] += sumarr[i][j + 1] + sumarr[i + 1][j] - sumarr[i + 1][j + 1]

ans = 0
for ij in range(19 * 19 - 1):
    i = ij // 19
    j = ij % 19
    for ij2 in range(ij, 19 * 19):
        i2 = ij2 // 19
        j2 = ij2 % 19

        if arr[i][j] * arr[i2][j2] == 0: continue

        if ij == ij2 and i + i2 >= 18 and j + j2 >= 18:
            ans += arr[i][j] * (arr[i][j] - 1) // 2
        else:
            if (arr[i][j] * arr[i2][j2] != 0 and i + i2 >= 18 and j + j2 >= 18):
                ans += arr[i][j] * arr[i2][j2]
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
N = int(input())

M = [[0] * 20 for _ in range(20)]

As = []
for _ in range(N):
    a = input()
    if '.' not in a:
        a += '.0'
    big, small = a.split('.')
    big = int(big)
    small = int((small + '000000000')[:9])
    A = big * 10 ** 9 + small

    bai2 = 0
    while A % 2 == 0:
        bai2 += 1
        A //= 2
        if bai2 >= 18:
            break
    bai5 = 0
    while A % 5 == 0:
        bai5 += 1
        A //= 5
        if bai5 >= 18:
            break
    As.append((bai2, bai5))
    M[0][0] += 1
    M[0][bai5+1] -= 1
    M[bai2+1][0] -= 1
    M[bai2+1][bai5+1] += 1

# imosu hou
M2 = map(lambda row: list(accumulate(row)), M)
M3 = map(lambda col: list(accumulate(col)), zip(*M2))
M4 = list(zip(*M3))

ans = 0
for bai2, bai5 in As:
    ans += M4[18-bai2][18-bai5]
    if bai2 >= 9 and bai5 >= 9:
        ans -= 1
print(ans // 2)

Submission status: Accepted

Solution code:
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	D = defaultdict(int)
	table = [[0] * 100 for i in range(100)]
	tablesum = [[0] * 100 for i in range(100)]
	for i in range(N):
		A = input()
		num = ""
		mod5 = 0
		mod2 = 0
		for j in range(len(A)):
			if A[-1 - j] == ".":
				mod5 -= j
				mod2 -= j
			else:
				num += A[-1 - j]

		num = int(num[::-1])
		while True:
			if num % 2 == 0:
				mod2 += 1
				num = int(num // 2)
			else:
				break
		while True:
			if num % 5 == 0:
				mod5 += 1
				num = int(num // 5)
			else:
				break

		table[50 + mod2][50 + mod5] += 1
		tablesum[50 + mod2][50 + mod5] += 1
		# print(mod2, mod5)

	ans = 0
	# 累積
	for i in range(98, -1, -1):
		for j in range(98, -1, -1):
			tablesum[i][j] += tablesum[i + 1][j]

	for i in range(98, -1, -1):
		for j in range(98, -1, -1):
			tablesum[i][j] += tablesum[i][j + 1]

	for i in range(1, 100):
		for j in range(1, 100):
			if i >= 50 and j >= 50:
				ans += table[i][j] * (tablesum[100 - i][100 - j] - table[i][j])
			else:
				ans += table[i][j] * tablesum[100 - i][100 - j]
			# if table[i][j] * tablesum[100 - i][100 - j] > 0:
				# print(i, j)
				# print(table[i][j], tablesum[100 - i][100 - j])

	for i in range(50, 100):
		for j in range(50, 100):
			ans += (table[i][j] - 1) * table[i][j]

	# print(ans)
	ans = int(ans // 2)
	print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

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

n = int(input())

memo = [[0 for i in range(19)] for j in range(19)]
for i in range(n):
    ai = input().rstrip('\n')
    if '.' in ai:
        a1, a2 =  ai.split('.')
        a2 = a2 + '000000000'
        ai = a1 + a2[:9]
    else:
        ai = ai + '000000000'
    ai = int(ai)
    c2 = 0
    c5 = 0
    while True:
        if ai % 2 or c2 == 18:
            break
        ai = ai // 2
        c2 += 1
    while True:
        if ai % 5 or c5 == 18:
            break
        ai = ai // 5
        c5 += 1
    memo[c2][c5] += 1

ans1 = 0
ans2 = 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 or j != l:
                        ans2 += memo[i][j] * memo[k][l]
                    else:
                        ans1 += max(memo[i][j] * (memo[k][l]-1), 0)

print(ans2 // 2 + ans1 // 2)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
def factor(n, m=None):
    # mを与えると、高々その素因数まで見て、残りは分解せずにそのまま出力する
    arr = defaultdict(int)
    temp = n
#     M = int(-(-n**0.5//1))+1
#     if m is not None:
#         M = min(m+1, M)
    M = 6
    for i in range(2, M):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt

    return arr

n = int(input())
a = [None]*n
m = [[0]*19 for _ in range(19)]
ab = [None]*n
for i in range(n):
    s = input()
    if "." in s:
        ind = s.index(".")
        vv = len(s) - s.index(".") - 1
        v = int(s[:ind])*10**(vv) + int(s[(ind+1):])
        v *= 10**(9-vv)
    else:
        v = int(s)*10**9
    d = factor(v, 5)
    d.setdefault(2,0)
    d.setdefault(5,0)
    a,b = max(0, 18-d[2]), max(0, 18-d[5])
    m[a][b] += 1
    ab[i] = (d[2],d[5])
def cumsum2(v):
    # v: h*wの2次元リスト
    h,w = len(v), len(v[0])
    v.insert(0, [0]*w)
    for l in v:
        l.insert(0, 0)
    for i in range(1,h+1):
        for j in range(1,w+1):
            v[i][j] = v[i-1][j] + v[i][j-1] - v[i-1][j-1] + v[i][j]
    return v
m = cumsum2(m)
ans = 0
for a,b in ab:
#     print(a,b)
    ans += m[min(19,a+1)][min(19,b+1)]
    if a>=9 and b>=9:
        ans -= 1
print(ans//2)

Submission status: Accepted

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

n=int(input())
a=[]
for i in range(n):
    x=input().rstrip()
    if '.' in x:
        y=x.split('.')
        x=int(y[0])*10**9+int(y[1])*10**(9-len(y[1]))
    else:
        x=int(x)*10**9
    a.append(x)

b=[]
for i in a:
    x=i
    count2=0
    while x%2==0:
        x=x//2
        count2+=1
    count5 = 0
    while x % 5 == 0:
        x = x // 5
        count5 += 1

    b.append((count2,count5))

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

for i in b:
    imos[0][0]+=1
    imos[i[0]+1][0]-=1
    imos[0][i[1]+1]-=1
    imos[i[0]+1][i[1]+1]+=1

for i in range(49):
    for j in range(49):
        imos[i][j+1]+=imos[i][j]
for j in range(49):
    for i in range(49):
        imos[i+1][j]+=imos[i][j]

ans=0
for i in b:
    x=18-i[0]
    y=18-i[1]
    x=max(x,0)
    y=max(y,0)
    ans+=imos[x][y]

for i in b:
    if i[0]*2>=18 and i[1]*2>=18:
        ans-=1

ans=ans//2
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y


N = int(readline())
A = [None]*N
temp = read().split()
for i,s in enumerate(temp):
    s = s.decode().rstrip()
    if '.' in s:
        a,b = s.split('.')
        n = int(a+b)*10**(9-len(b))
    else:
        n = int(s)*10**9
    A[i] = n

def conv(n):
    c2 = 0
    while n%2 == 0:
        n //= 2
        c2 += 1
    c5 = 0
    while n%5 == 0:
        n //= 5
        c5 += 1
    return (c2,c5)

A = [conv(a) for a in A]
grid = [[0]*19 for _ in range(19)]

for x,y in A:
    grid[min2(x,18)][min2(y,18)] += 1

temp = [[0]*20 for _ in range(19)]
for i in range(19):
    c = 0
    for j in reversed(range(19)):
        c += grid[i][j]
        temp[i][j] = c

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

for j in range(20):
    c = 0
    for i in reversed(range(19)):
        c += temp[i][j]
        acc[i][j] = c

cnt = 0
for x,y in A:
    p,q = max2(0,18-x),max2(0,18-y)
    cnt += acc[p][q]
    if x*2 >= 18 and y*2 >= 18:
        cnt -= 1

print(cnt//2)

Submission status: Accepted

Solution code:
n = int(input())
a = []
howmany = [[0] * (19) for _ in range(19)]
for i in range(n):
    x = input()
    len_x = len(x)
    if '.' in x:
        idx = x.index('.')
        x = int(x.replace('.', '') + '0' * (9 - len_x + idx + 1))
    else:
        x = int(x)
        x = x * 10 ** 9
    #print(x)
    cnt_2, cnt_5 = 0, 0
    while x % 2 == 0:
        x //= 2
        cnt_2 += 1
    while x % 5 == 0:
        x //= 5
        cnt_5 += 1
    cnt_2 = min(cnt_2, 18)
    cnt_5 = min(cnt_5, 18)
    howmany[cnt_2][cnt_5] += 1
    a.append((cnt_2, cnt_5))

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

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

#print(*howmany, sep='\n')

cnt = 0
for i in range(n):
    l, r = a[i]
    if l >= 9 and r >= 9:
        cnt += howmany[18-l][18-r] - 1
    else:
        cnt += howmany[18-l][18-r]


print(cnt // 2)

Submission status: Accepted

Solution code:
n = int(input())
twos = [0]*n
fives = [0]*n


table = [[0 for _ in range(100)] for _ in range(100)]
table_acm = [[0 for _ in range(100)] for _ in range(100)]
offset = 20

def divisor(x,mod):
    ret = 0
    while True:
        if x % mod == 0:
            x //= mod
            ret+=1
        else:
            return ret

def factor(x):
    two = 0
    five = 0
    if '.' not in x:
        y = int(x)
        two = divisor(y,2)
        five = divisor(y,5)
    else:
        order = x.find('.')
        order = len(x) - 1 - order
        two = -order
        five = -order
        y = int(x.replace(".",""))
        two += divisor(y,2)
        five += divisor(y,5)
    return (two,five)

for i in range(n):
    x = input()
    two,five = factor(x)
    table[two+offset][five+offset] += 1
    table_acm[two+offset][five+offset] += 1

for i in range(99,0,-1):
    for j in range(99,0,-1):
        table_acm[i-1][j-1] = table_acm[i-1][j] + table_acm[i][j-1] - table_acm[i][j] + table[i-1][j-1]

ret = 0
for i in range(100):
    for j in range(100):
        ret += table[i][j] * table_acm[max(2*offset - i,0)][max(2*offset - j,0)]

#print(table_acm[offset][offset])
print((ret-table_acm[offset][offset])//2)

Submission status: Accepted

Solution code:
# Fast IO (only use in integer/float input)

# import os,io
# input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

constant = 10 ** 9

N = int(input())
numList = []
for _ in range(N):
    a = float(input())
    numList.append(round(constant * a))

ListTwoandFive = [] # 2 and 5 index
ListTwoandFivePartialSum = [] # sum of upper rectangle

for i in range(19):
    ListTwoandFive.append([])
    ListTwoandFivePartialSum.append([])
    for j in range(19):
        ListTwoandFive[i].append(0)
        ListTwoandFivePartialSum[i].append(0)

for elem in numList:
    cnt2 = 0
    cnt5 = 0
    while elem % 2 == 0:
        elem //= 2
        cnt2 += 1
    while elem % 5 == 0:
        elem //= 5
        cnt5 += 1
    ListTwoandFive[min(cnt2,18)][min(cnt5,18)] += 1

for i in range(18,-1,-1):
    for j in range(18,-1,-1):
        if i == 18 and j == 18:
            ListTwoandFivePartialSum[i][j] = ListTwoandFive[i][j]
        elif i == 18:
            ListTwoandFivePartialSum[i][j] = ListTwoandFive[i][j] + ListTwoandFivePartialSum[i][j+1]
        elif j == 18:
            ListTwoandFivePartialSum[i][j] = ListTwoandFive[i][j] + ListTwoandFivePartialSum[i+1][j]
        else:
            ListTwoandFivePartialSum[i][j] = ListTwoandFive[i][j] + ListTwoandFivePartialSum[i+1][j] +\
                 ListTwoandFivePartialSum[i][j+1] - ListTwoandFivePartialSum[i+1][j+1]

cnt = 0

for i in range(19):
    for j in range(19):
        cnt += ListTwoandFive[i][j] * ListTwoandFivePartialSum[18 - i][18 - j]


cnt -=  ListTwoandFivePartialSum[9][9]
cnt //= 2

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
numbers = [[0] * 39 for _ in range(39)]
offset = 19
for _ in range(n):
    a = input()
    log2 = 0
    log5 = 0
    if '.' in a:
        b, c = a.split('.')
        log2 -= len(c)
        log5 -= len(c)
        d = int(b + c)
    else:
        d = int(a)
    while d % 2 == 0:
        d //= 2
        log2 += 1
    while d % 5 == 0:
        d //= 5
        log5 += 1
    log2 = min(log2, 19)
    numbers[log2 + offset][log5 + offset] += 1

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

for i in range(37, -1, -1):
    acc[i][-1] = numbers[i][-1] + acc[i + 1][-1]

for j in range(37, -1, -1):
    acc[-1][j] = numbers[-1][j] + acc[-1][j + 1]

for i in range(37, -1, -1):
    for j in range(37, -1, -1):
        acc[i][j] = numbers[i][j] + acc[i + 1][j] + acc[i][j + 1] - acc[i + 1][j + 1]

ans = 0

for i in range(39):
    for j in range(39):
        if numbers[i][j] == 0:
            continue
        log2 = i - offset
        log5 = j - offset
        pi = -log2 + offset
        pj = -log5 + offset
        tmp = acc[pi][pj]
        if pi <= i and pj <= j:
            tmp -= 1
        ans += numbers[i][j] * tmp

ans //= 2
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
data=[[0]*50 for i in range(50)]

for i in range(n):
    s=input()
    l=len(s)
    num=0
    sho=0
    keta=1
    for i in range(l):
        if(s[l-i-1]!='.'):
            num+=keta*int(s[l-i-1])
            keta*=10
        else:
            sho=i
    #print(num,sho)
    two=-sho
    five=-sho
    for i in range(100):
        if(num%2==0):
            two+=1
            num//=2
        else:
            break
    for i in range(100):
        if(num%5==0):
            five+=1
            num//=5
        else:
            break
    #print(two,five)
    data[two+9][five+9]+=1


ans=0
for i in range(50):
    for j in range(50):
        jibun=data[i][j]
        if(jibun==0):
            continue
        aite=0
        for p in range(max(0,18-i),50):
            for q in range(max(0,18-j),50):
                aite+=data[p][q]
                if(p==i and j==q):
                    aite-=1
        ans+=jibun*aite
        #print(i-9,j-9,jibun,aite)

print(ans//2)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
A = []
for _ in range(N):
    a = LS2()
    if not '.' in a:
        a = int(''.join(a))
        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))
    else:
        i = a.index('.')
        l = len(a)
        del a[i]
        a += ['0']*(9-l+1+i)
        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 - 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:
import sys
readline = sys.stdin.readline

G = 10**10
lai = 0
def Decimal(x):
    global lai
    a = x.strip().split('.')
    if len(a) == 1 or all([ai == '0' for ai in a[1]]):
        lai += 1
        return int(a[0])*G
        
    lf = len(a[1])
    i, f = map(int, a)
    return (i*10**(lf) + f)*10**(10-lf)
    
    
N = int(readline())
A = [Decimal(readline()) for _ in range(N)]

H = 200
geta = 100
Grid = [[0]*H for _ in range(H)]
i25 = []


for af in A:
    i2 = -10
    i5 = -10
    while af%2 == 0:
        af //= 2
        i2 += 1
    while af%5 == 0:
        af //= 5
        i5 += 1
    i25.append((i2, i5)) 


for i2, i5 in i25:
    Grid[geta+i2][geta+i5] += 1

for i in range(geta+90, geta-90, -1):
    for j in range(geta+90, geta-90, -1):
        Grid[i][j] += Grid[i][j+1]

for j in range(geta+90, geta-90, -1):
    for i in range(geta+90, geta-90, -1):
        Grid[i][j] += Grid[i+1][j]


ans = 0
for i2, i5 in i25:
    ans += Grid[geta-i2][geta-i5]
    #print(i2, i5, Grid[geta-i2][geta-i5])
print((ans-lai)//2)

Submission status: Accepted

Solution code:
grid=[]
for i in range(19):
  grid.append([])
  for j in range(19):
    grid[-1].append(0)
n=int(input())
twos=[]
fives=[]
for i in range(n):
  t=input()
  predec=[]
  afdec=[]
  flag=0
  for j in range(len(t)):
    if t[j]=='.':
      flag=1
      continue
    if flag==0:
      predec.append(t[j])
    if flag==1:
      afdec.append(t[j])
  s=int(''.join(predec))*(10**9)
  if len(afdec)>0:
    s+=int(''.join(afdec))*(10**(9-len(afdec)))
  twos=0
  while s%2==0 and twos<18:
    twos+=1
    s=s//2
  fives=0
  while s%5==0 and fives<18:
    fives+=1
    s=s//5
  grid[twos][fives]+=1
ans=0
for i in range(19):
  for j in range(19):
    for k in range(18-i,19):
      for l in range(18-j,19):
        ans+=grid[i][j]*grid[k][l]
    if i>=9 and j>=9:
      ans-=grid[i][j]
print(ans//2)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())

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

def get25(p):
  n2 = 0
  n5 = 0
  while p % 2 == 0:
    n2 += 1
    p //= 2
  while p % 5 == 0:
    n5 += 1
    p //= 5
  return (n2, n5)

d = defaultdict(int)

for i in range(N):
  s = input()
  for i, c in enumerate(s):
    if c == '.':
      q = int(s[:i] + s[i+1:])
      p = 10 ** (len(s) - i - 1)
      break
  else:
    q = int(s)
    p = 1
  g = gcd(p, q)
  p, q = p // g, q // g
  p2, p5 = get25(p)
  q2, q5 = get25(q)
  

  d[(q2 - p2, q5 - p5)] += 1
  # print(q, p, q2, p2, q5, p5)

# print(d)

d = list(d.items())

ans = 0

# print(d)

for j in range(len(d)):
  if d[j][0][0] >= 0 and d[j][0][1] >= 0:
    ans += d[j][1] * (d[j][1] - 1) // 2
  for i in range(j):
    if d[i][0][0] + d[j][0][0] >= 0 and d[i][0][1] + d[j][0][1] >= 0:
      # print(d[i], d[j])
      ans += d[i][1] * d[j][1]

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = []
for i in range(N):
    X = input()
    if "." in X:
        XL = X.split(".")
        XN = len(XL[1])
        X = int(XL[0])*10**XN+int(XL[1])
        Y = X*10**(9-XN)
    else:
        Y = int(X)*10**9
    A.append(Y)
T = [[0]*2 for i in range(N)]
max2 = 0
max5 = 0
for i in range(N):

    X = A[i]
    cnt = 0
    while X%5==0:
        cnt+=1
        X = X//5
    T[i][0]=cnt
    max5 = max(max5,cnt)

    X = A[i]
    cnt = 0
    while X%2==0:
        cnt+=1
        X = X//2
    T[i][1]=cnt
    max2 = max(max2,cnt)

S = [[0]*(max2+1) for i in range(max5+1)]

for i in range(N):
    S[T[i][0]][T[i][1]]+=1

out = 0
for j1 in range(max2+1):
    for i1 in range(max5+1):
        for j2 in range(max2+1):
            for i2 in range(max5+1):
                X = S[i1][j1]
                Y = S[i2][j2]
                if i1+i2>=18 and j1+j2>=18:
                    if i1==i2 and j1==j2:
                        out += X*(X-1)
                    else:
                        out += X*Y
print(out//2)

Submission status: Accepted

Solution code:
from itertools import groupby
from operator import itemgetter
import sys
input = sys.stdin.readline
read = sys.stdin.read

N = int(input())
geta = 10**9
A = [int(round(float(input())*geta)) for _ in range(N)]
geta2 = geta * geta

B = []
for a in A:
    twoes = (a & -a).bit_length() - 1
    a >>= twoes
    fives = 0
    while a % 5 == 0:
        a //= 5
        fives += 1
    B.append((twoes, fives))

B.sort()
#print(B)
idx_r = N-1
Five = [0] * 19
ans = 0
for l2, group in groupby(B, key=itemgetter(0)):
    while idx_r >= 0:
        r2, r5 = B[idx_r]
        if r2 + l2 < 18:
            break
        Five[r5 if r5<=18 else 18] += 1
        idx_r -= 1
    #print(Five)
    for _, l5 in group:
        #print((18-l5) if l5<=18 else 0)
        ans += sum(Five[(18-l5) if l5<=18 else 0:])
        if l2>=9 and l5>=9:
            ans -= 1
print(ans//2)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


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

    class Bit:
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x):
            while i <= self.size:
                self.tree[i] += x
                i += i & -i

        def lower_bound(self, w):
            if w <= 0:
                return 0
            x = 0
            k = 1 << (self.size.bit_length() - 1)
            while k:
                if x + k <= self.size and self.tree[x + k] < w:
                    w -= self.tree[x + k]
                    x += k
                k >>= 1
            return x + 1

    N = int(input())
    A = []
    for _ in range(N):
        A.append(input().rstrip('\n'))

    TF = []
    for a in A:
        if "." not in a:
            t = f = 0
            a = int(a)
            while True:
                if a%2 == 0:
                    t += 1
                    a //= 2
                else:
                    break
            while True:
                if a%5 == 0:
                    f += 1
                    a //= 5
                else:
                    break
        else:
            a0, a1 = a.split(".")
            if int(a1) == 0:
                t = f = 0
                a0 = int(a0)
            else:
                a1 = [s for s in a1]
                while a1:
                    if a1[-1] == "0":
                        a1.pop()
                    else:
                        break
                a1 = "".join(a1)
                t = f = -len(a1)
                a0 = int("".join([a0, a1]))
            while True:
                if a0%2 == 0:
                    t += 1
                    a0 //= 2
                else:
                    break
            while True:
                if a0%5 == 0:
                    f += 1
                    a0 //= 5
                else:
                    break
        TF.append((t, f))

    Q = []
    for q in TF:
        t, f = q
        Q.append((t, f, 0))
        Q.append((-t, -f, 1))
    Q.sort(key=lambda x: x[2])
    Q.sort(key=lambda x: x[1], reverse=True)
    Q.sort(key=lambda x: x[0], reverse=True)
    bit = Bit(50)
    ans = 0
    for t, f, x in Q:
        if x == 0:
            bit.add(f+10, 1)
        else:
            ans += bit.sum(50) - bit.sum(f+10-1)
            if t <= 0 and f <= 0:
                ans -= 1
    print(ans // 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin

N = int(input())

dic = {}
lis = [[0] * 19 for i in range(19)]
ans = 0

for loop in range(N):

    S = stdin.readline()
    S = S[:-1]

    if "." not in S:
        num = int(S) * (10**9)
    else:
        x,y = S.split(".")
        yy = int(y) * (10**(9-len(y)))
        xx = int(x) * 10**9
        num = xx+yy
    #print (num)

    two = 0
    five = 0
    if num == 0:
        continue
    while num % 2 == 0:
        num //= 2
        two += 1
    while num % 5 == 0:
        num //= 5
        five += 1

    for i in range(19):
        for j in range(19):
            if i+two >= 18 and j+five>=18:
                ans += lis[i][j]
    lis[min(18,two)][min(18,five)] += 1
    #lis[two][five] += 1

print (ans)