Jap

Vom considera toate numerele naturale intre 2 si N inclusiv care nu pot fi scrise sub forma x^y, unde y diferit de 1. Notam aceasta multime cu numere S. Pentru fiecare din aceste numere vom calcula puterea maxima la care poate fi ridicat astfel incat rezultatul sa fie ≤ N. Pentru un numar i, vom considera ca aceasta putere este j (deci i^j ≤ N) si vom incerca sa calculam cate elemente distincte se pot genera ridicand fiecare din elementele i¹, i², i³, ..., i^j la puteri intre 1 si M. Astfel pentru i va trebui sa calculam cate elemente distincte are secventa i¹, i², ..., i^M, i^2*1, i^2*2, ..., i^2*M, ..., i^j*1, i^j*2, ..., i^j*M. Observam ca oricum am alege x si y din multimea S, secventele generate cu regula de mai sus vor fi complet disjuncte, si in plus reuniunea tuturor secventelor va constitui intreaga secventa data in enunt. Astfel, suma numarului de elemente distincte determinate pentru fiecare x din S va reprezenta numarul cerut in enunt.

Setul S poate fi determinat, parcurgand elementele de la 2 la N si marcand toate puterile mai mari ca 1 al elementului curent ca nefacand parte din set. Determinarea setului S are complexitate O(N).

De aici putem elabora mai multe solutii de complexitati diferite:

• O(N) precalculare, O(N * M * log(N * M)) pe test - 20 de puncte

Pentru fiecare i din S, calculam j, cel mai mare numar natural astfel incat i^j ≤ N, adaugam puterile 1, 2, 3, ..., M, 2, 4, 6, ..., 2M, ..., j, 2j, 3j, ..., jM intr-un vector, il sortam si adunam la rezultat numarul de elemente distincte din el.

• O(N) precalculare, O(N log N) pe test - 50 de puncte

Pentru fiecare i, vom calcula numarul de elemente distincte din secventa corespunzatoare lui folosind principiul includerii si excluderii. Fie A un subset al multimii [1, 2, 3, ..., j]. Vom calcula comun[A] = numarul de puteri aflate in intersectia tuturor secventelor (x*1, x*2, x*3, ..., x*M), pentru x apartinand lui A. Intersectia acestor secvente trebuie sa contina numai elemente ≤ M * min(A), unde min(A) = elementul minim din subsetul A, si numai elemente divizibile cu lcm(A), unde lcm(A) reprezinta cel mai mic multiplu comun al elementelor din A. Astfel comun[A] va fi egal cu [M * min(A) / lcm(A)], unde [x] reprezinta partea intreaga a lui x.

Acum, conform principiului includerii si excluderii. putem determina numarul de elemente distincte ale secventei corespunzatoare lui i, adunand comun[A] pentru toate subseturile A avand numar impar de elemente si scazand comun[A] pentru toate subseturile A avand numar par de elemente.

Observam ca pentru multe numere din setul S, puterea maxima j la care poate fi ridicat astfel incat rezultatul sa fie ≤ N se repeta si vom calcula comun[A] de multe ori pentru aceleasi subseturi. Pentru a evita acest lucru putem calcula valorile lui comun la inceput, pentru orice subset al multimii [1, 2, 3, ..., log₂ N] si mentine rez[x] = numarul de elemente distincte din secventa generata de un element i din S pentru care puterea maxima este egala cu x.

Complexitatea totala devine O(2^{log N} log N)) precalcularea lui comun + O(N) adunarea sumelor, deci O(N log N).

• O(N + nr_M_distinct * N log N) precalculare, O(N) pe test - 70 de puncte

Observam ca valorile lui comun si rez depind doar de M si deci le putem calcula doar pentru fiecare M diferit din fisierul de intrare.

• O(N + nr_M_distinct * N log N) precalculare, O(log² N) pe test - 100 de puncte

Am observat deja ca daca 2 numere diferite i si j din setul S au aceeasi putere maxim j la care pot fi ridicate fara sa depaseasca N, numarul de elemente distincte din secventa generata de fiecare dintre ele este egal.

In loc sa parcurgem toate elementele din S, putem numara pentru fiecare putere j de la 1 la log₂ N cate numere din S au aceasta putere maxima. Pentru fiecare putere putem determina limitele sale inferioare si superioare prin cautare binara si, precalculand nrInS[i] = cate numere naturale ≤ i sunt in setul S, putem determina cate elemente sunt in S intre cele 2 limite. Complexitate finala pe test O(log² N).

Observatie

Este posibil sa ajungem la un query time de O(1).
Astfel, sa presupunem ca pentru fiecare putere pana in logN stim cate duplicate sunt generate de un numar care este putere maxima.
( exemplu: pentru exponentul egal cu 4, stim ca avem x duplicate. Atunci daca inmultim numarul de numere care sunt puteri la a patra ( 16, 81, etc ) cu x o sa avem numarul de duplicate date de puterile la a patra. Daca facem asta pentru fiecare putere p pana in logN, si adaugam la rezultat, obtinem rezultatul query-ului pentru un N dat.
In primul rand, pentru fiecare n <= N si p <= logN, putem precalcula cate puteri la a p-a sunt <= n, in O( N log N ). De asemenea, putem
preprocesa fiecare query posibil in O(N log N) [ nu avem decat sa stocam produsul "cate puteri la a p-a sunt <= n" * "cate duplicate sunt pentru p"].
Tinand cont ca O(N log N) necesitam oricum pentru fiecare M distinct, ajungem la un query time de O(1).

Sper ca s-a inteles :)

Solutie alternativa

A doua solutie calculeaza care sunt puterile i pentru care uⁱ poate fi scris ca v^j cu v < u si j ≤ M. Prima conditie pe care trebuie sa o indeplineasca u, este sa se scrie de forma p₁^f1 * ... * p_t^ft unde cmmdc(f₁, ..., f_t) = d, d ≠ 1. Daca notam w radicalul de ordin d al lui u, atunci uⁱ se va scrie ca w^d*i, ba chiar mai mult se va scrie ca (w^q)^i*d/q unde q divide d.
Pornind de la aceste observatii putem calcula pentru un M fixat cate numere distincte generaza (w^d)ⁱ pentru fiecare d in parte ( d este maxim log₂N, adica 16). (w^d)ⁱ se poate scrie in functie de w^q cu q < d, daca i e divizibil cu q/cmmdc(d, q), adica i*d multiplu al lui cmmmc(d, q). Asadar pentru fiecare d intre 2 si 16 si q intre 1 si d, vom insemna intr-un tablou ca puterea k*cmmmmc(d, q), unde k * cmmmc(d, q) / q <= M este duplicat pentru orice u = w^d.
Acum mai trebuie sa calculam pentru toate valorile de la 1 la N care este cmmdc-ul puterilor factorilor (adica d). Aceasta se poate face foarte repede sub forma asemanatoare cu ciurul lui Eratostene, numerele care au d > 1 pot fi scrise ca un numar mai mic ridicat la o putere si in loc sa adunam, inmultim.
Cu acest algoritm calculam dintr-o data toate query-urile care au acelasi M.
Complexitatea finala este O(nr_M_distinct * (M log² N + N log N)). O implementare atenta a acestei solutii va lua 100 de puncte.