Vizualizare sursă pentru „3752 - Cvintete”

Se consideră numerele naturale nenule <code>N</code> și <code>D</code> urmate de o secvență <code>S</code> de <code>N</code> numere naturale nenule ordonate crescător, indexate de la <code>1</code> la <code>N</code>.

= Cerința =
Să se determine numărul de cvintete de indici <code>(i1, i2, i3, i4, i5)</code> ce verifică relațiile:

* <code>a • b • c = D</code>
* <code>a • x2</code> <code>+ b • y2</code> <code>= c2</code>
* <code>a < b < c</code>
* <code>x ≠ y</code>

unde am notat cu <code>a = S[i1]</code>, <code>b = S[i2]</code>, <code>c = S[i3]</code>, <code>x = S[i4]</code>, <code>y = S[i5]</code>. Rezultatul se va afișa modulo <code>1.000.000.007</code>.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține pe prima linie două numere naturale nenule <code>N</code> și <code>D</code> cu semnificația

din enunț. Pe următoarea linie se vor afla <code>N</code> numere naturale nenule ordonate crescător.

= Date de ieșire =
Fișierul de ieșire <code>output.txt</code> va conține un singur număr natural care reprezintă rezultatul cerinței, modulo <code>1.000.000.007</code>.

== Exemplul 1 ==
input.txt:

4 6

1 2 3 3

output.txt:

2

Explicație:

Cvintetele care respectă cerința sunt: <code>(1, 2, 3, 1, 2)</code>, <code>(1, 2, 4, 1, 2)</code>.

== Exemplul 2 ==
input.txt:

10 60

1 2 3 4 4 5 6 8 10 12

output.txt:

4

Explicație:

Cvintetele care respectă cerința sunt: <code>(1, 6, 10, 8, 4)</code>, <code>(1, 6, 10, 8, 5)</code>, <code>(1, 7, 9, 2, 4)</code>, <code>(1, 7, 9, 2, 5)</code>

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
import math

M = 1000000007
N = 25000
P = 1235789

def gcd(A, B):
    r = A % B
    while r != 0:
        A = B
        B = r
        r = A % B
    return B

def main():
    with open("input.txt", "r") as infile, open("output.txt", "w") as outfile:
        n, d = map(int, infile.readline().split())
        f = [0] * (N + 1)
        di = [0] * (N + 1)
        pp = [0] * (N + 1)
        v = [0] * (P + 1)
        k = 0
        m = 0

        l=list(map(int, infile.readline().split()))

        for i in range(n):
            x = l[i]
            f[x] += 1
            if x > m:
                m = x

        for i in range(1, m + 1):
            if (d % i == 0) and (f[i] > 0):
                k += 1
                di[k] = i
            pp[i] = i * i
            v[pp[i] % P] = i

        sol = 0

        for i in range(1, k - 1):
            a = di[i]
            for j in range(i + 1, k):
                b = di[j]
                e = a * b
                if d % e == 0:
                    c = d // e
                    if c > b and c <= m and f[c] > 0:
                        nr = f[a] * f[b] * f[c]
                        w = c * c
                        dc = gcd(a, b)
                        if w % dc == 0:
                            l = int(math.sqrt(w / b))
                            for u in range(1, l + 1):
                                if (w - b * pp[u]) % a == 0:
                                    z = (w - b * pp[u]) // a
                                    h = v[z % P]
                                    if h * h == z and h != u and h <= m:
                                        sol += nr * f[u] * f[h]

        outfile.write(str(sol % M) + "\n")

if __name__ == "__main__":
    main()

</syntaxhighlight>