# PBinfo #4508 – Eratostene10 – Rezolvare C++

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

## Enunț

Cerința
Se dau două șiruri A și B, fiecare format din câte N numere naturale, și un număr natural R. Aflați numărul perechilor (i,j) pentru care restul împărțirii numărului Ai la Bj este R.

Date de intrare
Programul citește de la tastatură numerele N și R, apoi N numere naturale reprezentând șirul A, apoi încă N numere naturale reprezentând șirul B.

Date de ieșire
Programul va afișa pe ecran numărul perechilor (i,j) pentru care restul împărțirii numărului Ai  la Bj este R.

Restricții și precizări

1 ≤ N ≤ 100.000
0 ≤ R ≤ 10
1 ≤ Ai , Bj ≤ 1.000.000

Exemplu:
Intrare

5 3
12 17 23 54 81
9 7 2 10 17 
Ieșire

4
Explicație
Perechile de indici (i, j), pentru care restul împărțirii numărului Ai la Bj este 3, sunt: (1, 1), (2, 2), (3, 4), (4, 5).

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
long long d;
int n,r,i,j,z;
int a[100003],b[100003],v[1000020],c[1000020];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> r;
    for(i = 1; i <= n; i++)
        cin >> a[i];
    for(i = 1; i <= n; i++)
    {
        cin >> b[i];
        if(b[i]>r){z++; v[b[i]]++;}
    }
    for(i = 1; i <= 1000000; i++)
    {
        j = i;
        while(j+r <= 1000000)
        {
            c[j+r] += v[i];
            j = j+i;
        }
    }
    for(i = 1; i <= n; i++)
    {
        d += c[a[i]];
        if(a[i]==r) d += z;
    }
    cout << d;
    return 0;
}
```

## Resurse

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