Problem: 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.

Submission attempts (in order):
from bisect import bisect_left
from decimal import Decimal

N, *A = map(Decimal, open(0).read().split())
N = int(N)
A.sort()

c = {}
intc = 0
ints = []
decs = []
for d in A:
    if d in c:
        c[d] += 1
        if d == int(d):
            intc += 1
    else:
        c[d] = 1
        if d == int(d):
            intc += 1
            ints.append(d)
        else:
            decs.append(d)

result = intc * (intc - 1) // 2
for i in range(len(decs)):
    a = decs[i]
    t = bisect_left(decs, 1 / a)
    for j in range(t, len(decs)):
        b = decs[j]
        t = a * b
        if t == int(t):
            #print(a, b)
            result += c[a] * c[b]

    f = a - int(a)
    t = bisect_left(ints, 1 / f)
    for j in range(t, len(ints)):
        b = ints[j]
        t = a * b
        if t == int(t):
            #print(a, b)
            result += c[a] * c[b]

print(result)


from bisect import bisect_left
from decimal import Decimal

N, *A = map(Decimal, open(0).read().split())
N = int(N)
A.sort()

c = {}
intc = 0
ints = []
decs = []
for d in A:
    if d in c:
        c[d] += 1
        if d == int(d):
            intc += 1
    else:
        c[d] = 1
        if d == int(d):
            intc += 1
            ints.append(d)
        else:
            decs.append(d)

print(intc)
result = intc * (intc - 1) // 2
for i in range(len(decs)):
    a = decs[i]
    if a < 1:
        t = bisect_left(decs, 1 / a)
    else:
        t = i + 1
    for j in range(t, len(decs)):
        b = decs[j]
        t = a * b
        if t == int(t):
            #print(a, b)
            result += c[a] * c[b]

    if a < 1:
        t = bisect_left(ints, 1 / a)
    else:
        t = 0
    for j in range(t, len(ints)):
        b = ints[j]
        t = a * b
        if t == int(t):
            #print(a, b)
            result += c[a] * c[b]

print(result)


from bisect import bisect_left
from decimal import Decimal

N, *A = map(Decimal, open(0).read().split())
N = int(N)
A.sort()

c = {}
intc = 0
ints = []
decs = []
for d in A:
    if d in c:
        c[d] += 1
        if d == int(d):
            intc += 1
    else:
        c[d] = 1
        if d == int(d):
            intc += 1
            ints.append(d)
        else:
            decs.append(d)

result = intc * (intc - 1) // 2
for i in range(len(decs)):
    a = decs[i]
    f = a - int(a)
    t = bisect_left(decs, 1 / f)
    for j in range(t, len(decs)):
        b = decs[j]
        t = a * b
        if t == int(t):
            #print(a, b)
            result += c[a] * c[b]

    t = bisect_left(ints, 1 / f)
    for j in range(t, len(ints)):
        b = ints[j]
        t = a * b
        if t == int(t):
            #print(a, b)
            result += c[a] * c[b]

print(result)


from bisect import bisect_left
from decimal import Decimal

N, *A = map(Decimal, open(0).read().split())
N = int(N)
A.sort()

ints = [d for d in A if int(d) == d]
decs = [d for d in A if int(d) != d]

result = len(ints) * (len(ints) - 1) // 2
for i in range(len(decs)):
    a = decs[i]
    if a < 1:
        t = bisect_left(decs, 1 // a)
    else:
        t = i + 1
    for j in range(t, len(decs)):
        t = a * decs[j]
        if t == int(t):
            result += 1

    t = bisect_left(ints, 1 // a)
    for j in range(t, len(ints)):
        t = a * decs[j]
        if t == int(t):
            result += 1

print(result)


from decimal import Decimal

N, *A = map(Decimal, open(0).read().split())
N = int(N)

d = {}
for a in A:
    a = int(a * (10 ** 9))
    x = -9
    while a % 2 == 0:
        x += 1
        a %= 2
    y = -9
    while a % 5 == 0:
        y += 1
        a %= 5
    t = (x, y)
    d.setdefault(t, 0)
    d[t] += 1

result = 0
xs = d.values()
for i in range(len(xs)):
    x, y = xs[i]
    for j in range(i + 1, len(xs)):
        m, n = xs[j]
        if x + m >= 0 and y + n >= 0:
            result += d[xs[i]] * d[xs[j]]
print(result)


from decimal import Decimal

N, *A = map(Decimal, open(0).read().split())
N = int(N)

d = {}
for a in A:
    a = int(a * (10 ** 9))
    if a == 0:
        t = (0, 0)
    else:
        x = -9
        while a % 2 == 0:
            x += 1
            a //= 2
        y = -9
        while a % 5 == 0:
            y += 1
            a //= 5
        t = (x, y)
    d.setdefault(t, 0)
    d[t] += 1


result = 0
xs = list(d.keys())
for i in range(len(xs)):
    x, y = xs[i]
    t = d[xs[i]]
    if x >= 0 and y >= 0:
        result += t * (t - 1) // 2
    for j in range(i + 1, len(xs)):
        m, n = xs[j]
        if x + m >= 0 and y + n >= 0:
            result += t * d[xs[j]]
print(result)


Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Time Limit Exceeded

Accepted