# PBinfo #3752 – Cvintete – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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 ≠ y

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

Date de intrare
Fișierul de intrare cvintete.in conține pe prima linie două numere naturale nenule N și D cu semnificația
din enunț. Pe următoarea linie se vor afla N numere naturale nenule ordonate crescător.

Date de ieșire
Fișierul de ieșire cvintete.out va conține un singur număr natural care reprezintă rezultatul cerinței, modulo 1.000.000.007.

Subtask-uri

Subtask 1 (16 puncte): 1 ≤ N ≤ 20, 1 ≤ S[i] ≤ 20, 1 ≤ D ≤ 250
Subtask 2 (12 puncte): 1 ≤ N ≤ 1000, 1 ≤ S[i] ≤ 1000, 1 ≤ D ≤ 100.000
Subtask 3 (25 puncte): 1 ≤ N ≤ 5000, 1 ≤ D ≤ 10.000.000, S[i]=i, pentru orice 1 ≤ i ≤ N
Subtask 4 (28 puncte): 1 ≤ N ≤ 10.000, 1 ≤ S[i] ≤ 5000, 1 ≤ D ≤ 10.000.000
Subtask 5 (19 puncte): 1 ≤ N ≤ 100.000, 1 ≤ S[i] ≤ 20.000, 1 ≤ D ≤ 1.000.000.000
Pentru toate subtask-urile, se respectă relația S[i] ≤ S[i + 1], oricare ar fi 1 ≤ i ≤ N - 1.

Exemplul 1:
cvintete.in

4 6
1 2 3 3
cvintete.out

2
Explicație
Cvintetele care respectă cerința sunt: (1, 2, 3, 1, 2), (1, 2, 4, 1, 2).

Exemplul 2:
cvintete.in

10 60
1 2 3 4 4 5 6 8 10 12
cvintete.out

4
Explicație
Cvintetele care respectă cerința sunt: (1, 6, 10, 8, 4), (1, 6, 10, 8, 5), (1, 7, 9, 2, 4), (1, 7, 9, 2, 5)

## Cod sursă C++

```cpp
/*
   O(nr_tiplete x N) cu c*c : gcd(a, b)
   nr_triplete calculate in O(nr_div^2), N - nr. de valori distincte
*/
# include <bits/stdc++.h>
using namespace std;
ifstream f("cvintete.in");
ofstream g("cvintete.out");
const int MOD = 1e9 + 7;
int s[100010];
int D[20001];
int ap[100010];
int apt[20001];
long long p[100010];
struct triplet
{
    int x,y,z;
} T[20001];
int n, N, M, K;
long long nr, d;
void formtrip()
{
    int i, j, k;
    for(k=K; k>=2; k--)
    {
        i = 1, j = k - 1;
        while (i < j)
        {
            long long x = 1LL * D[i] * D[j] * D[k];
            if (x == d)
            {
                T[++N] = {D[i], D[j], D[k]};
                apt[N] = (ap[D[i]] * ap[D[j]] * ap[D[k]]);
                i++, j--;
            }
            else if (x < d) i++;
                       else j--;
        }
    }
}
long long gcd(long long a, long long b)
{
    while (b)
    {
        long long r = a % b;
        a = b; b = r;
    }
    return a;
}
long long ec(int a, int b, int c)
{
    int nr = 0, i = 1, j = n;
    j = lower_bound(p, p+n+1, c / b) - p;
    if (j < 0 || j > n) j = n;
    while (i <= n && j > 0)
    {
        long long x = 1LL * a * p[i] + 1LL * b * p[j];
        if (x == c)
        {
            if (s[i] != s[j])
            {
                nr = (nr + 1LL * (ap[s[i]] * ap[s[j]]));
            }
            i++, j--;
        }
        else if (x < c) i++;
                   else j--;
    }
    return nr;
}
int main()
{
    int i, j, k;
    long long x, y = 0;
    f >> n >> d;
    n = 0;
    while (f >> x)
    {
        y = x;
        if (ap[x] == 0)
        {
            s[++n] = x;
            p[n] = 1LL * x * x;
            ap[x] = 1;
            if (d % x == 0) D[++K] = x;
        } else ap[x]++;
    }
    formtrip();
    for(i=1; i<=N; i++)
    {
        long long a, b, c;
        a = T[i].x;
        b = T[i].y;
        c = T[i].z * T[i].z;
        if (c % gcd(a, b) == 0)
        {
            x = ec(a, b, c);
            nr = ( nr + 1LL * apt[i] * x );
        }
    }
    g << nr % MOD;
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3752)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3752/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3752/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)