Miawinator: Pagină nouă: Se consideră numerele naturale nenule `N` și `D` urmate de o secvență `S` de `N` numere naturale nenule ordonate crescător, indexate de la `1` la `N`. = Cerința = Să se determine numărul de cvintete de indici `(i1, i2, i3, i4, i5)` ce verifică relațiile: * `a • b • c = D` * `a • x2` `+ b • y2` `= c2` * `a < b < c` * `x...`


2024-01-05T01:43:50Z
Pagină nouă: 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...
New page
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>
3752 - Cvintete - Revision history
