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) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def primes(n):
    a = Counter()
    while n % 2 == 0:
        a[2]+=1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a[f]+=1
            n //= f
        else:
            f += 2
    if n != 1:
        a[n]+=1
    return a
def daccumulate(s):#二次元累積和
    n=len(s); m=len(s[0])
    acc=[[0]*m for _ in range(n)]
    for i in range(n):
        si=s[i]; ai=acc[i]
        for j in range(m):
            tot=si[j]
            if i>0: tot+=acc[i-1][j]
            if j>0:
                tot+=ai[j-1]
                if i>0: tot-=acc[i-1][j-1]
            ai[j]=tot
    return acc

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(str, input().split())) #1行ベクトル
    A = tuple(input() for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    ans=0
    dp=[[0]*19 for _ in range(19)]
    t9=10**9
    bas=100

    for a in A:
        ta=0


        ta=round(float(a)*t9)

        n2=0
        n5=0
        while ta%2==0:
            n2+=1
            ta//=2
        while ta%5==0:
            n5+=1
            ta//=5


        n2=min(18,n2)
        n5=min(18,n5)
        dp[18-n2][18-n5]+=1
    ddp=daccumulate(dp)
    ans=0

    for i in range(19):
        for j in range(19):
            t2=18-i
            t5=18-j
            c=dp[t2][t5]
            ta=ddp[i][j] 
            if i*2>=18 and j*2>=18:
                ta-=c
                ans+=c*(c-1)
            ans+=ta*c

    print(ans//2)
               




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False


def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n = onem()

num = []

data = [[0 for i in range(50)] for j in range(60)]

base = 9
for i in range(n):
	po = input()[:-1]
	if not "." in po:
		aaa = int(po)
		tw = 0
		while aaa % 2 == 0:
			tw += 1
			aaa //= 2
		fi = 0
		while aaa % 5 == 0:
			fi += 1
			aaa //= 5
		num.append([tw + base,fi + base])
		data[tw + base][fi + base] += 1
	else:
		for j in range(len(po)):	
			if po[-(j+1)] != "0":
				po = po[:len(po)-j]
				break
			if po[-(j+1)] == ".":
				break
		for j in range(len(po)):
			if po[j] == ".":
				size = len(po)-1 - j
				break
		aaa = int(po.replace(".", ""))		
		tw = 0
		while aaa % 2 == 0:
			tw += 1
			aaa //= 2
		fi = 0
		while aaa % 5 == 0:
			fi += 1
			aaa //= 5
		
		num.append([tw-size + base,fi-size + base])
		data[tw-size + base][fi-size + base] += 1


for i in range(60):
	for j in range(49,0,-1):
		data[i][j-1] += data[i][j]


cou = 0
for i in num:
	a,b = i
	base = 9
	if a-base >= 0 and b-base >= 0:
		cou -= 1
	a -= base
	b -= base
	if a > 9:
		a = 9
	if b > 9:
		b = 9
	a *= -1
	a += base
	b *= -1
	b += base
	for j in range(a,60):
		cou += data[j][b]
print(cou//2)

Submission status: Accepted

Solution code:
from decimal import *

n = int(input())
ans = 0
vec = [Decimal(input()) for i in range(n)]
vec25 = [[0 for i in range(50)] for i in range(50)]  # 整数にするのに余っている2,5の数
for i in range(n):
    a = int(vec[i] * 1000000000)
    num2 = -9
    num5 = -9
    while a%2 == 0:
        a //= 2
        num2 += 1
    while a%5 == 0:
        a //= 5
        num5 += 1
    vec25[num2][num5] += 1
for i in range(-9, 40): 
    for j in range(-9, 20):
        for k in range(max(-9, -i), 40):
            for l in range(max(-9, -j), 20):
                if i+k >= 0 and j+l >= 0 :
                    if i != k or j != l :
                        ans += vec25[i][j] * vec25[k][l]
                    else :
                        ans += vec25[i][j] * (vec25[i][j] - 1)
ans //= 2
print(ans)

Submission status: Accepted

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


class BIT():
    def __init__(self, n, x=1):
        self.n = n
        self.T = [[0]*20 for _ in [0]*20]

    def add(self, i, y, x):
        i += 1
        y += 1
        while i <= self.n:
            j = y
            while j <= self.n:
                self.T[i][j] += x
                j += j & -j
            i += i & -i

    def _sum(self, i, y):
        i += 1
        y += 1
        ret = 0
        while i > 0:
            j = y
            while j > 0:
                ret += self.T[i][j]
                j ^= j & -j
            i ^= i & -i
        return ret

    def sum(self, i, j):
        return self._sum(18, 18) - self._sum(i-1, 18) - self._sum(18, j-1) + self._sum(i-1, j-1)


ans = 0
B = BIT(19)


def fact(n):
    cnt2 = cnt5 = 0
    for _ in range(18):
        if n % 2:
            break
        n //= 2
        cnt2 += 1
    for _ in range(18):
        if n % 5:
            break
        n //= 5
        cnt5 += 1
    return cnt2, cnt5


for a in A:
    if '.' in a:
        a, b = a.split('.')
        cnt2 = cnt5 = 9 - len(b)

        a = int(a) * (10**len(b)) + int(b)
        c2, c5 = fact(a)
        cnt2 += c2
        cnt5 += c5
    else:
        cnt2 = 9
        cnt5 = 9

        a = int(a)
        c2, c5 = fact(a)
        cnt2 += c2
        cnt5 += c5

    cnt2 = min(18, cnt2)
    cnt5 = min(18, cnt5)

    ans += B.sum(18-cnt2, 18-cnt5)
    B.add(cnt2, cnt5, 1)

print(ans)

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

Z = np.zeros((20,20), dtype=int)

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

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

answer = 0
for a in A:
  c2 = count2(a)
  c5 = count5(a)
  t2 = max(18-c2,0)
  t5 = max(18-c5,0)
  #answer += np.sum(Z[t2:,t5:])
  #Z[min(19,c2),min(19,c5)] += 1
  answer += Z[t2,t5]
  Z[:min(19,c2)+1,:min(19,c5)+1] += 1

print(answer)

Submission status: Accepted

Solution code:
def f(x):
  r=[0,0]
  n=x
  while x%2==0:
    r[0]+=1
    x//=2
  while x%5==0:
    r[1]+=1
    x//=5
  return r

N=int(input())
A=[input() for i in range(N)]
for i in range(N):
  if not('.' in A[i]):
    A[i]=int(A[i])*10**9
  else:
    A[i]=list(A[i].split('.'))
    A[i]=int(A[i][0])*10**9+int(A[i][1])*10**(9-len(A[i][1]))
for i in range(N):
  A[i]=f(A[i])
X=[[0]*50 for i in range(50)]
for i in range(N):
  X[A[i][0]][A[i][1]]+=1
C=[[0]*51 for i in range(51)]
for i in range(50):
  for j in range(50):
    C[i+1][j+1]=C[i+1][j]+C[i][j+1]-C[i][j]+X[i][j]
P=0
for i in range(N):
  A[i]=[max(18-A[i][0],0),max(18-A[i][1],0)]
  P+=C[-1][-1]-C[-1][A[i][1]]-C[A[i][0]][-1]+C[A[i][0]][A[i][1]]
  if max(A[i])<=9:
    P-=1
print(P//2)

Submission status: Accepted

Solution code:
import sys
#from fractions import Fraction
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def a(s):
	if s.count('.')==0:
		n2=0
		n5=0
		v = int(s)
	else:
		p = s.index('.')
		n2 = -(len(s) - p - 1)
		n5 = -(len(s) - p - 1)
		if p == 1 and s[0]=='0':
			v= int(s[2:])
		else:
			v = int(s[:p]+s[p+1:])
	while v % 2 == 0:
		v = v//2
		n2+=1
	while v % 5 == 0:
		v = v//5
		n5+=1
	return str(n2)+'_'+str(n5)

def main():
	n = int(input())
	#b , c = tin()
	al = [a(input()) for _ in range(n)]
	cal = collections.Counter(al)
	#pa(cal)
	ret = 0
	pp = set()
	for k in cal:
		for k2 in cal:
			if k+'_'+k2 in pp:
				continue
			#pa((vi*vj)/(10**20))
			if k==k2:
				a2, a5 = map(int, k.split('_'))
				if a2>=0 and a5 >= 0:
					ret += cal[k]*(cal[k]-1)//2
			else:
				a2, a5 = map(int, k.split('_'))
				b2, b5 = map(int, k2.split('_'))
				if a2+b2 >= 0 and a5+b5 >= 0:
					ret += cal[k]*cal[k2]
				
			pp.add(k+'_'+k2)
			pp.add(k2+'_'+k)
			#pa((k,k2,ret))
			
	return ret
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

OFS=20
KK = 41
n = inn()
d = [[0]*KK for i in range(KK)]
for i in range(n):
    a = ins()
    p = a.find('.')
    if p<0:
        v = int(a)
        k = 0
    else:
        b = a[:p]+a[p+1:]
        v = int(b)
        k = len(a)-1-p
    x2 = 0
    while v%2==0:
        x2 += 1
        v //= 2
    x2 = min(x2,OFS)
    x5 = 0
    while v%5==0:
        x5 += 1
        v //= 5
    x5 = min(x5,OFS)
    d[x2-k+OFS][x5-k+OFS] += 1

#if DBG:
#    for i in range(KK):
#        for j in range(KK):
#            if d[i][j]!=0:
#                ddprint(f"i {i-OFS} j {j-OFS} {d[i][j]}")

ans = 0
h = {}
for p in range(KK):
    for q in range(KK):
        sm = 0 if p<OFS or q<OFS else (d[p][q]*(d[p][q]-1)//2)
        #if sm>0:
        #ddprint(f"p {p-OFS} q {q-OFS} d {d[p][q]} {sm=}")
        for r in range(-p+2*OFS,KK):
            #if r==p:
            #    continue
            for s in range(-q+2*OFS,KK):
                if (r,s)==(p,q) or (r,s,p,q) in h:
                    continue
                h[(p,q,r,s)] = 1
                sm += d[p][q]*d[r][s]
                #if d[p][q]*d[r][s]>0:
                #    ddprint(f"p {p-OFS} q {q-OFS} r {r-OFS} s {s-OFS} d {d[p][q]} {d[r][s]}")
        ans += sm
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
G=[[0]*20 for i in range(45)]
A=[0,0,0,0]
for i in range(n):
  S=list(input())
  s=""
  f=0
  a=0
  for j in S:
    if j==".":
      f=1
    else:
      s=s+j
      if f==1:
        a=a+1
  A[0]=int(s)
  A[1]=a
  m=int(s)
  c=0
  while m%10==0:
    c=c+1
    m=m//10
  A[0]=m
  A[1]-=c
  m=A[0]
  c=0
  while m%2==0:
    c=c+1
    m=m//2
  A[2]=c
  c=0
  m=A[0]
  while m%5==0:
    c=c+1
    m=m//5
  A[3]=c
  G[A[2]-A[1]+9][A[3]-A[1]+9]+=1
B=[[0]*21 for i in range(46)]
for i in range(44,-1,-1):
  for j in range(19,-1,-1):
    B[i][j]=B[i+1][j]+B[i][j+1]-B[i+1][j+1]+G[i][j]
ans=0
for i in range(45):
  for j in range(20):
    ans=ans+G[i][j]*B[max(0,18-i)][max(0,18-j)]
    if i>=max(0,18-i) and j>=max(0,18-j):
      ans=ans-G[i][j]
print(ans//2)

Submission status: Accepted

Solution code:

n = int(input())
T = 45
F = 19
a = [[0 for i in range(F)] for j in range(T)]
p = pow(10,9)
two_size = 18
five_size = 18
count = 0
for i in range(n):
    s = input()
    if '.' in s:
        index = s.index('.')
        s += '0' * (  9 - (len(s) - 1 - index))
        s = s.replace('.','')
    else :
        s += '0' * 9
    k = int(s)
    two = 0
    five = 0
    while k % 2 == 0:
        two += 1
        k //= 2
    while k % 5 == 0:
        five += 1
        k //= 5
    t, f = two_size - two, five_size - five
    for x in range(t, T):
        for y in range(f, F):
            count += a[x][y]
    a[two][five] += 1
print(count)

Submission status: Accepted

Solution code:
import math
def prime2(x):
  cnt = 0
  while x % 2 == 0:
    x //= 2
    cnt += 1
  return cnt
def prime5(x):
  cnt = 0
  while x % 5 == 0:
    x //= 5
    cnt += 1
  return cnt


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

D = [[0] * 3 for _ in range(N)]

M2 = 0
M5 = 0
Md = 0

cnt = 0
for x in A:
  t = x.find(".")
  d = 9
  if t != -1:
    for i in range(t):
      x = x.rstrip("0")
    d -= (len(x) - t - 1)
    x = x.replace(".", "")
  p2 = prime2(int(x))
  p5 = prime5(int(x))
  n = min(p2, p5)
  p2 -= n
  p5 -= n
  d += n
  D[cnt] = [p2, p5, d]
  cnt += 1
  M2 = max(M2, p2)
  M5 = max(M5, p5)
  Md = max(Md, d)

Md += 1
M = min(M2, M5) + 1
L = [[[0] * M for _ in range(2)] for _ in range(Md)]

ans = 0
for i in range(N):
  p2, p5, d = D[i]
  if p2 == 0:
    n = 1
    t = p5
  else:
    n = 0
    t = p2
  for j in range(Md):
    for k in range(M):
      if d + j + min(t, k) >= 18:
        ans += L[j][1 - n][k]
      if d + j >= 18:
        ans += L[j][n][k]
  L[d][n][min(t, M - 1)] += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import decimal
import numpy as np
input = sys.stdin.readline

N = int(input())
A = []
C2 = np.array([[0 for j in range(30)] for i in range(14)])  # 10countは9タス
C5 = np.array([[0 for j in range(30)] for i in range(14)])
C10 = np.zeros(14)
for _ in range(N):
    i = decimal.Decimal(input())
    c10, c2, c5 = 0, 0, 0
    while i % 1 != 0:
        c10 -= 1
        i *= 10
    while i % 10 == 0:
        c10 += 1
        i /= 10
    while i % 2 == 0:
        c2 += 1
        i /= 2
    while i % 5 == 0:
        c5 += 1
        i /= 5
    c2 = min(c2, 30)
    c5 = min(c5, 30)
    A.append((c10, c2, c5))
    C2[c10+9][c2] += 1
    C5[c10+9][c5] += 1
    C10[c10+9] += 1

ans = 0
for i in range(14):
    ans += C10[i]*np.sum(C10[18-i:])
    if i >= 9:
        ans -= C10[i]
    for j in range(18-i):
        if j >= 14:
            continue
        for k in range(1, 30):
            shouldhave = 18 - i - j
            if k >= shouldhave:
                ans += C2[i][k] * np.sum(C5[j][shouldhave:])
                ans += C5[i][k] * np.sum(C2[j][shouldhave:])

print(int(ans//2))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import math

n = int(input())
a_top = [[], []]
a_base = [[], []]
for _ in range(n):
    s = input().rstrip()
    if "." not in s:
        top = int(s)
        base = 1
    else:
        dot = s.index(".")
        length = len(s)
        lower_num = len(s) - dot - 1
        top = int(s.replace(".", ""))
        base = pow(10, lower_num)
    gcd = math.gcd(top, base)
    top = top // gcd
    base = base // gcd
    twos = 0
    fives = 0
    while top % 2 == 0:
        twos += 1
        top //= 2
    while top % 5 == 0:
        fives += 1
        top //= 5
    a_top[0].append(twos)
    a_top[1].append(fives)
    twos = 0; fives = 0
    while base % 2 == 0:
        twos += 1
        base //= 2
    while base % 5 == 0:
        fives += 1
        base //= 5
    a_base[0].append(twos)
    a_base[1].append(fives)

nums = dict()
offset = 16
field = [[0] * 35 for _ in range(35)]
for tt, tf, bt, bf in zip(a_top[0], a_top[1], a_base[0], a_base[1]):
    if tt - bt > 15:
        twos = 15
    else:
        twos = tt - bt
    if tf - bf > 15:
        fives = 15
    else:
        fives = tf - bf
    field[twos + offset][fives + offset] += 1

single = 0
double = 0
for i in range(35):
    for j in range(35):
        for k in range(35):
            for l in range(35):
                if i == k and j == l:
                    if i - offset + k - offset >= 0 and j - offset + l - offset >= 0:
                        double += field[i][j] * (field[i][j] - 1)
                else:
                    if i - offset + k - offset >= 0 and j - offset + l - offset >= 0:
                        double += field[i][j] * field[k][l]
print(single + double // 2)

Submission status: Accepted

Solution code:
n = int(raw_input())
G = []

for i in range(39):
    G.append([])
    for j in range(39):
        G[i].append(0)

ans = 0
    
for i in range(n):
    c2 = 0
    c5 = 0
    s = raw_input()
    if not '.' in s:
        p = int(s) * (10**18)
    else:
        a,b = s.split('.')
        x = len(b)
        p = int(a+b)*(10**(18-x))
    #print p
    while (p%2==0):
        p/=2
        c2+=1
    while (p%5==0):
        p/=5
        c5+=1
    c2 = min(c2,36)
    c5 = min(c5,36)
    for j in range(37):
        for k in range(37):
            if (j+c2 >= 36 and k+c5 >= 36):
                ans += G[j][k]
    G[c2][c5] += 1
print ans

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import gcd
n = int(input())
li = []
for i in range(n):
    s = input()
    if '.' in s:
        a, b = s.split('.')
        t = 10 ** len(b)
        li.append((int(a) * t + int(b), t))
    else:
        li.append((int(s), 1))
p = [[0] * 35 for _ in range(35)]
cnt = 0
for i in range(n):
    x, y = li[i]
    g = gcd(x, y)
    x //= g
    y //= g
    if y == 1:
        cnt += 1
    li[i] = x
    a1, b1 = 0, 0
    while x % 2 == 0:
        a1 += 1
        x //= 2
    while x % 5 == 0:
        b1 += 1
        x //= 5
    a2, b2 = 0, 0
    while y % 2 == 0:
        a2 += 1
        y //= 2
    while y % 5 == 0:
        b2 += 1
        y //= 5
    p[a1 - a2 + 9][b1 - b2 + 9] += 1
ans = 0
for i in range(0, 35):
    for j in range(0, 35):
        for a in range(max(0, 18 - i), 35):
            for b in range(max(0, 18 - j), 35):
                ans += p[i][j] * p[a][b]
print((ans - cnt) // 2)

Submission status: Accepted

Solution code:
from math import *
#import sys 
#cin = sys.stdin()

cnt = [[0] * 20 for i in range(20)]

ans = 0
for _ in range(int(input())):
    t = input().strip().split('.')
    if (len(t) > 1):
        b = int(t[0])*1000000000 + int(t[1]) * 10 ** (9 - len(t[1]))
    else:
        b = int(t[0]) * 1000000000
    x, y = 0, 0
    while (b % 2 == 0) and (x <= 18):
        x += 1
        b //= 2
    while (b % 5 == 0) and (y <= 18):
        y += 1
        b //= 5
    #print(x, y)
    for i in range(20):
        for j in range(20):
            if (i + x >= 18) and (j + y >= 18):
                ans += cnt[i][j]
    cnt[x][y] += 1
print(ans)

Submission status: Accepted

Solution code:
import bisect as bi
n=int(input())
l=[input() for i in range(n)]
sto=[]
numl=[[0 for j in range(19)] for i in range(19)]
intcnt=0
for i in range(n):
    s=l[i]
    pal=[0,0]
    if "." not in s:
        pass
    else:
        cs=len(s)-s.index(".")-1
        pal=[-cs,-cs]
    N=int(s.replace(".",""))
    while N%5 == 0:
        N//=5
        pal[0]+=1
    while N%2 == 0:
        N//=2
        pal[1]+=1
    numl[min(18,pal[0]+9)][min(18,pal[1]+9)]+=1
    sto.append(pal)
    if pal[0]>=0 and pal[1]>=0:intcnt+=1
ans=0
accnuml=[[0 for i in range(20)] for j in range(20)]
for i in range(1,20):
    for j in range(1,20):
        accnuml[i][j]=accnuml[i][j-1]+accnuml[i-1][j]-accnuml[i-1][j-1]+numl[i-1][j-1]
for i in range(n):
    x,y=sto[i][0],sto[i][1]
    ans+=n-(accnuml[min(max(0,-x+9),18)][-1]+accnuml[-1][min(max(0,-y+9),18)]-accnuml[min(18,max(0,-x+9))][min(18,max(0,-y+9))])
print((ans-intcnt)//2)

Submission status: Accepted

Solution code:
#a
from decimal import Decimal
def comp_index(x, p, maxim):
    low = 0
    high = maxim

    while low + 1 < high:
        mid = (low + high) // 2
        guess = x // p ** mid == x / p ** mid
        if guess:
            low = mid
        else:
            high = mid
    return low
n = int(input())
ansans = 0
max2 = 44
max5 = 19
a = [[0] * (2*max5+1) for _ in range(2*max2+1)]
a_ac = [[0] * (2*max5+1) for _ in range(2*max2+1)]
for _ in range(n):
    aratio = Decimal(input()).as_integer_ratio()
    a2 = -comp_index(aratio[1], 2, max2)
    if a2 == 0:
        a2 = comp_index(aratio[0], 2, max2)
    a5 = -comp_index(aratio[1], 5, max5)
    if a5 == 0:
        a5 = comp_index(aratio[0], 5, max5)
    a[a2][a5] += 1
    a_ac[a2][a5] += 1
    if a2 >= 0 and a5 >= 0:
        ansans -= 1
for i in range(max2, -max2-1, -1):
    for j in range(max5-1, -max5-1, -1):
        a_ac[i][j] += a_ac[i][j+1]
for j in range(max5, -max5-1, -1):
    for i in range(max2-1, -max2-1, -1):
        a_ac[i][j] += a_ac[i+1][j]
for i in range(-max2, max2+1):
    for j in range(-max5, max5+1):
        ansans += a[i][j] * a_ac[-i][-j]
#for i in range(-max2, max2+1):print(''.join(str(a[i][j]) for j in range(-max5+1, max5+1)))
#print()
#for i in range(-max2, max2+1):print(''.join(str(a_ac[i][j]) for j in range(-max5+1, max5+1)))
print(ansans//2)

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        #A1 ... AnのBIT(1-indexed)
        self.BIT = [0] * (n + 1)
        self.n = n

    #A1 ~ Aiまでの和 O(logN)
    def query(self, idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx & (-idx)
        return res_sum

    #Ai += x O(logN)
    def add(self, idx, x):
        while idx <= self.n:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return
def get_int(f):
    if "." not in f:
        return int(f),0
    return int(f.replace(".","")),len(f)-f.index(".")-1
n = int(input())
p = []
for i in range(n):
    a, b = get_int(input())
    c, d = 0, 0
    while a % 2 == 0:
        c += 1
        a //= 2
    while a % 5 == 0:
        d += 1
        a //= 5
    c -= b
    d -= b
    p.append((c, d))
p.sort()
now = n - 1
t = BIT(200)
ans = 0
for i in range(n):
    for j in range(now, i, -1):
        if p[i][0] + p[j][0] >= 0:
            t.add(-p[j][1] + 100, 1)
            now -= 1
        else:
            break
    if now < i:
        t.add(-p[i][1] + 100, -1)
    ans += max(0, t.query(100 + p[i][1]))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
M = [[0]*20 for _ in range(20)]
M2 = [[0]*20 for _ in range(20)]

for _ in range(N):
    A = input()
    x = 0
    decLen = 0

    if '.' in A:
        p = A.index('.')
        decLen = len(A) - p - 1
        x = int(A[:p])*10**decLen + int(A[p+1:])
    else:
        x = int(A)

    f2, f5 = -decLen, -decLen
    while(x%2 == 0):
        x /= 2
        f2 += 1

    while(x%5 == 0):
        x /= 5
        f5 += 1

    f2 = min(f2, 9)
    f5 = min(f5, 9)

    M[f2+9][f5+9] += 1



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


ans = 0
for i in range(19):
    for j in range(19):
#        if M[i][j] > 0:
#            print(i, j, M[i][j], M2[18-i][18-j])

        ans += M[i][j]*M2[18-i][18-j]
        if i >= 9 and j >= 9:
            ans -= M[i][j]

print(ans//2)

Submission status: Accepted

Solution code:
from itertools import product
from collections import defaultdict
inpl = lambda: list(map(int,input().split()))
N = int(input())
X = defaultdict(int)
for _ in range(N):
    S = input()
    if '.' in S:
        S = S.rstrip('0')
        S = S.rstrip('.')
    if '.' in S:
        T, U = S.split('.')
        m = len(U)
        p = q = -m
        a = int(T+U)
    else:
        p = q = 0
        a = int(S)
    while a % 2 == 0 and p < 9:
        p += 1
        a //= 2
    while a % 5 == 0 and q < 9:
        q += 1
        a //= 5
    X[(p,q)] += 1

ans = 0
for p in range(-9,10):
    for q in range(-9,10):
        for s in range(-9,10):
            for t in range(-9,10):
                if p == s and q == t:
                    if p >= 0 and q >= 0:
                        ans += X[(p,q)] * (X[(p,q)]-1)
                elif p + s >= 0 and q + t >= 0:
                    ans += X[(p,q)] * X[(s,t)]

print(ans//2)

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

import math
from collections import defaultdict

def main():
	n=II()
	#A=[]
	#B=[]
	d=defaultdict(int)

	for _ in range(n):
		x=float(input())
		x*=10**9
		x=int(x+0.5)
		g=math.gcd(x,10**9)
		#print(g)
		a=math.gcd(x//g,10**9)
		b=10**9//g
		#A.append(math.gcd(x//g,10**9))
		#B.append(10**9//g)
		d[(a,b)]+=1
	#print(A,B,d)

	ans=0

	for k,v in d.items():
		for kk,vv in d.items():
			if k!=kk:
				if (k[0]*kk[0])%(k[1]*kk[1])==0:
					#print(k,v,kk,vv)
					ans+=v*vv


	ans//=2

	for k,v in d.items():
		if k[1]==1:
			ans+=v*(v-1)//2

	print(ans)





















if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
import math
import bisect

def query_value(s):
    #print('s: %s' % s)
    pos = s.find('.')
    if (pos == -1):
        return int(s) * 10 ** 9
    ans = int(s[:pos])
    #print('ans: %d' % ans)
    for i in range(pos + 1, pos + 10):
        #print('i: %d' % i)
        #print('len(%s): %d' % (s, len(s)))
        if i >= len(s):
            ans *= 10
        else:
            #print('s[%d] = %s' % (i, s[i]))
            ans = ans * 10 + ord(s[i]) - ord('0')
            #ans *= 10
    return ans

def main():
    n = 18
    A = []
    for i in range(2*n):
        A.append([0] * (2*n))
    #print('A: %s' % str(A))
    for _ in range(int(input())):
        a = query_value(input())
        #print('a: %d' % a)
        p2 = 0
        p5 = 0
        while a % 2 == 0:
            p2 += 1
            a /= 2
        while a % 5 == 0:
            p5 += 1
            a /= 5
        A[p2][p5] += 1
        #print('p2: %d, p5: %d' % (p2, p5))
    ans = 0
    for x1 in range(2*n):
        for y1 in range(2*n):
            for x2 in range(2*n):
                for y2 in range(2*n):
                    if x1 == x2 and y1 == y2:
                        if A[x1][y1] > 0 and x1 + x2 >= n and y1 + y2 >= n:
                            #print('A[%d][%d]: %d, A[%d][%d]: %d' % (x1, y1, A[x1][y1], x2, y2, A[x2][y2]))
                            ans += A[x1][y1] * (A[x2][y2] - 1)
                            #print('ans: %d' % ans)
                    else:
                        if A[x1][y1] > 0 and A[x2][y2] > 0 and x1 + x2 >= n and y1 + y2 >= n:
                            #print('A[%d][%d]: %d, A[%d][%d]: %d' % (x1, y1, A[x1][y1], x2, y2, A[x2][y2]))
                            ans += A[x1][y1] * A[x2][y2]
                            #print('ans: %d' % ans)
    ans //= 2
    print(ans)
    '''
    for i in range(n):
        print('A[%d]: %s' % (i, str(A[i])))
    '''

if __name__ == "__main__":
    main()