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.
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena