Se dau două șiruri de numere naturale a[1], a[2], …, a[n] și b[1], b[2], …, b[m].

Cerința

Să se determine câte numere distincte au în comun cele două șiruri. De exemplu, șirurile a=(2,5,1,4,5,1) și b=(1,1,1,3,7,5) au în comun două numere distincte: 1 și 5.

Date de intrare

Programul citește de la tastatură numere naturale A, B, C, D, n, x, m, y. Cele două șiruri se generează astfel:

a[1] = x și, pentru i ≥ 2, a[i] = A + (a[i-1] * C + D) % (B - A + 1)
b[1] = y și, pentru i ≥ 2, b[i] = A + (b[i-1] * C + D) % (B - A + 1)

Date de ieșire

Programul va afișa pe ecran numărul C, reprezentând câte numere distincte au în comun cele două șiruri.

Restricții și precizări

2 ≤ n, m ≤ 2 000 000
2 ≤ A, B, C, D, x, y ≤ 10 000 000

Exemplu

Intrare

1 30 17 16 50 2 60 14

Ieșire

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema h1:

#include <bits/stdc++.h>
#define P 999023
#define pb push_back
using namespace std;

vector<int> h[P];

inline void Adauga(int x)
{
    int r = x % P;
    for (auto w : h[r])
        if (w == x) return;
    h[r].pb(x);
}

inline int Cauta(int x)
{
    int r = x % P;
    unsigned i, L;
    L = h[r].size();
    for (i = 0; i < L; i++)
        if (h[r][i] == x)
        {
            h[r][i] = h[r][L-1];
            h[r].pop_back();
            return 1;
        }
    return 0;
}

int main()
{
    int A, B, C, D;
    int i, n, m, x, y, cnt;
    cin >> A >> B >> C >> D;
    cin >> n >> x >> m >> y;
    B = B - A + 1;
    Adauga(x);
    for (i = 2; i <= n; i++)
    {
        x = A + (1LL * x * C + D) % B;
        Adauga(x);
    }
    cnt = Cauta(y);
    for (i = 2; i <= m; i++)
    {
        y = A + (1LL * y * C + D) % B;
        cnt += Cauta(y);
    }
    cout << cnt << "\n";
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2627 h1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2627 h1 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2627 h1