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

4

#include <bits/stdc++.h>

using namespace std;

bitset<10000001> f1 , f2 , f;

int main()
{
    int A, B, C, D, n, x, m, y;
    cin >> A >> B >> C >> D >> n >> x >> m >> y;
    f1[x]=1 , f2[y]=1;
    for(int i = 0 ; i < n ; ++i)
    {
         x = A + (1LL * x * C + D) % (B - A + 1);
         f1[x]=1;
    }
    for(int i = 0 ; i < m ; ++i)
    {
         y = A + (1LL * y * C + D) % (B - A + 1);
         f2[y]=1;
    }
    int cnt=0;
    for(int i = 0 ; i < n ; ++i)
    {
         x = A + (1LL * x * C + D) % (B - A + 1);
         if(f1[x]==1 && f2[x]==1 && f[x]==0)
            cnt++ , f[x]=1;
    }
    cout << cnt;
    return 0;
}