ID #123 · Colecția InfoAs · Operatori și expresii

Problema Carte

Biblioteca județeană din Sibiu funcționează pe un sistem cu limitări din punct de vedere al memoriei. Din acest motiv, cărțile din baza de date a bibliotecii au atașate diferite coduri numerice prin care se pot determina ușor diferite informații de bază despre acestea, cum ar fi autorii sau editura. Pentru a reține autorii unei cărți, fiecărui autor îi este atribuit câte un număr prim **unic** pentru acesta, un exemplu fiind dat în tabelul de mai jos. Astfel, pentru o carte dată, se poate reține cu ușurință autorul sau autorii acesteia, înmulțind codurile fiecărui autor în parte care a contribuit la cartea respectivă. De exemplu, folosind tabelul de mai jos, dacă o carte are codul pentru autori `10`, atunci autorii săi sunt Ion Creangă și Marin Preda. Tot din punctul de vedere al limitărilor tehnice, cărțile din bibliotecă pot avea coduri doar numere naturale de la `2` la un număr `M`. Autor | Cod numeric atașat ---|--- Ion Creangă | `2` Liviu Rebreanu | `3` Marin Preda | `5` _Și așa mai departe…_ ## Cerință Se dă o listă cu codurile aferente a `n` autori, împreună cu două valori naturale `q` și `k`. Trebuie răspuns la `q` întrebări. Pornind de la numărul `k`, se vor genera `2 × q` numere, primele două corespunzând primei întrebări, următoarele două corespunzând întrebării numărul 2 și așa mai departe. Pentru o întrebare dată cu numerele `k1` și `k2`, să se determine numărul de coduri dintre `min(k1, k2)` și `max(k1, k2)` (inclusiv), care au ca autori pe cel puțin unul dintre cei `n` din listă. Pornind de la numărul `k`, cele `2 × q` numere generate se generează după formula `k = ((k × 666013) modulo 999983) + 1` (cu mențiunea că această valoare poate ieși din tipul de date `int` în timpul înmulțirii). Primul număr generat se consideră a fi `k`. ## Date de intrare Fișierul de intrare `carte.in` conține pe prima linie numerele naturale `n`, `q` și `k` separate prin câte un spațiu. Pe a doua linie se află `n` numere prime separate prin câte un spațiu, reprezentând codurile numerice aferente autorilor. ## Date de ieșire Fișierul de ieșire `carte.out` conține `q` numere separate prin câte un spațiu, prin care se răspunde în ordinea citirii la cele `q` întrebări. ## Restricții și precizări * `M = 1.000.000` * `2 ≤ k ≤ n ≤ 50.000` * `1 ≤ q ≤ 100.000` * `2 ≤ cele n numere ≤ 1.000.000` * Cele `n` numere aferente autorilor sunt numere distincte și prime