Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | pinex.in, pinex.out | Sursă | Arhiva Educationala |
| Autor | Arhiva Educationala | Adăugată de |  Serban Andrei Stan •savim |
| Timp execuţie pe test | 1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Principiul includerii si excluderii
Trebuie să răspundeţi la M întrebări de tipul: Dându-se două numere naturale A şi B, să se determine numărul de numere mai mici ca A şi prime cu B. Două numere naturale (x,y) sunt prime între daca cmmdc(x,y)=1.
Date de intrare
Fişierul de intrare pinex.in va conţine pe prima linie numărul M, reprezentând numărul de query-uri. Următoarele M linii vor conţine câte două numere A si B, cu semnificaţia din enunţ.
Date de ieşire
Fişierul de ieşire pinex.out va conţine M linii, pe linia i fiind răspunsul la a i-a întrebare.
Restricţii
- 1 ≤ M ≤ 500
- 1 ≤ A ≤ 1018
- 1 ≤ B ≤ 1012
- Pentru 30% din teste M ≤ 100, A,B ≤ 1 000
- Pentru 70% din teste A,B ≤ 109
Exemplu
| pinex.in | pinex.out |
|---|---|
| 3 10 5 20 6 50 30 | 8 7 14 |
Indicaţii de rezolvare
O primă soluţie are complexitate O(M*A*log(A+B)) şi ar obţine 30 de puncte. În acest caz vom parcurge toate numerele din intervalul (1,A), verificând pentru fiecare dacă are cmmdc-ul cu B egal cu 1. O sursă pe această idee se poate găsi aici.
Pentru o soluţie mai performantă trebuie implementat principiul includerii si excluderii, despre care puteţi citi pe wikipedia sau pe mathworld. Concret, presupunând că trebuie să raspundem la query-ul 20 6, o să ne intereseze numărul de numere divizibile cu 2, numărul de numere divizibile cu 3 şi numărul de numere divizibile cu 2 şi 3 mai mici decât 20. Numarul de numere divizibile cu x mai mici decat y va fi simplu [y/x] (parte intreagă din y/x). Soluţia noastră va fi reprezentată de A-Nr2-Nr3+Nr6, unde Nrx este numărul de numere divizibile cu x mai mici decât 20. Numărul de apariţii ale numerelor cu număr impar de factori primi se scad din soluţie, în timp ce pentru număr par de factori primi se adună. Tabelul de mai jos ilustrează cele spuse până acum, o casută (p,q) fiind marcată dacă p divide q.
Această abordare are complexitate O(T*NRMAXF*2NRMAXF) şi obţine 70 de puncte. Prin NRMAXF ne referim la numărul maxim de factori primi ce poate să îi aibă numărul B.
Pentru punctaj maxim trebuie să aducem îmbunatăţiri soluţiei precedente. În primul rând, atunci când determinăm factorii primi ai lui B, ne vom uita pana la sqrt(B). Cum această valoare este mai mică decât 1 000 000, putem precalcula numerele prime prin care vom itera la fiecare query. Altă optimizare utilă nu doar la această problemă este să precalculăm puterile lui 2 pentru backtracking-ul care ne determina soluţia. O astfel de soluţie ce obţine 100 de puncte se află aici.
Aplicaţii
Mins
Jap
Secventa farey
Cowfood
Rifleman sgu
