infoarena

Aici puteţi discuta despre problema NrDivUnique (http://infoarena.ro/problema/nrdivunique).

hint rezolvare 100 ?  :ok: complexitate mai mica decat O ( a ) ?

dupa parerea mea problemele sunt cam grele  :'(  :readthis:

Uite rezolvarea mea:
Am observat ca daca b>=2*a, fiecare numar de la 1 la b sigur e divizor al intervalului. Asta e usor de demonstrat cu principiul cutiei.
Daca b<=2*a trebuie sa cautam care numere mai mici ca a nu divid nici un numar din [a,b]
Observam ca aceste numere sunt cele astfel incat [(a-1)/x]=[b/x], pentru ca nu va mai aparea nici un multiplu de-al sau in intervalul [a,b]
Asa ca putem face un for de la 1 la sqrt(b) sa eleminam numerele de la 1 la b care respecta aceasta chestie si observam cateva cazuri:

I Daca [(a-1)/i]=[b/i] eliminam 1 de la rezultat(adica pe i)
II Fie
x=[(a-1)/i]
y=[b/i]
u=[(a-1)/(i+1)]
v=[b/(i+1)]

Toate numerele mai mari ca v dau cel mult i in raportul [b/k] (k>=v)
Toate numerele mai mici sau egal cu x dau cel putin i in raportul [(a-1)/i] (k<=x)
Deci toate numerele k apartinand lui (v;x] au proprietatea [(a-1)/k]=[b/k]

Deci nu trebuie decat sa scadem din rezultatul curent cate numere sunt in intervalul (v;x] (atentie v deschis)
Si inca o precizare. Deoarece vom merge la sqrt(b) trebuie ca la orice moment sa nu scadem vreun interval care sa contine vreuna din elementele <=sqrt(b). Deci v=max(sqrt(b),[b/(i+1)]
Si inca ceva:vezi sa nu scazi elementele unui interval daca el nu are sens(adica v>=x)

Presupun ca asta e si rezolvarea oficiala.

P.S:Problema asta e foarta usoara, insa la intensitate avand in vedere ca maximul a fost 30 trebuie sa recunosc ca a fost cam grea

L.E: Ambele cazuri trebuie luate in considerare(in paralel). Deci daca primul caz se adevereste asta nu inseamna ca nu mai trebuie sa consideram si al doilea sau invers.:D

Salut!

Cred ca ar trebui marita putin limita la aceasta problema, deoarece am o solutie in O(N*sqrt(B)) (cand B<=10^6) si nu reusesc sa trec de 80 de puncte. Totodata, am observat ca sursele ce au luat 100 recent sunt chiar la limita (48 ms pe testul maxim). Multumesc anticipat! :)