524 Numar de Divizori

[•astronomy]

Aici puteţi discuta despre problema Numar de Divizori.

[•Sycron]

....

la aceasta problema am calculat divizorii de la 2 la n/2 ptr fiecare numar din interval si la nr de div obtinuti am adaugat 2*(b-a+1) adica divizorii 1 si el insusi..

primesc numai 10 puncte.. restul time exceded si primul test incorect

[•astronomy]

Incearca sa gasesti un algoritm mai eficient, vezi ca este si un articol in care se gaseste solutia la problema asta.

[•Sycron]

da, am gasit solutia... ms

totusi vroiam sa o gandesc eu .. dar cum e rezolvata acolo nu o gandeam asa niciodata

[•zalman]

si eu patesc aceeasi poveste...iau doar 30 de pct...am incercat sa il imbunatatesc putin (testez daca nr e prim si atunci nu mai caut toti divizorii)...dar tot 30 ...
"vezi ca este si un articol in care se gaseste solutia la problema asta."....unde pot sa o gasesc?...

[•wefgef]

Intri pe pagina problemei si te uiti unde a fost propusa (sus, in dreapta paginii, unde scrie "Sursa"). Apoi intri la sectiunea Articole de pe infoarena, si cauti concursul respectiv. Dai click, si ai in fata articolul cu solutii. 

[•ooctav]

"Solutia se bazeaza pe faptul ca aceste numere se repeta pe anumite intervale. Astfel se iau toate numerele i de la 1 la sqrt(N) si se vor tine intr-un vector sortate valorile: i si N/i."
nu inteleg ... mi se pare ca termenii (N/i) de la 1 la sqrtN sunt cu totii diferiti 
si cum se formeaza vectoru nu inteleg 

[•andrici_cezar]

numarul de divizori poate sa treaca 2 miliarde la problema asta?

[•CezarMocan]

Da, ai nevoie de long long pentru rezultat (cel putin eu am folosit).

[•cosmina_yup]

Salut! M-am apucat si eu de aceasta problema. Am rezolvat-o corect spun eu, am verificat pe mai multe exemple. Iau la ea doar 10 puncte, iar la majoritatea imi scrie :"Killed by SIGNAL11" sau "Time limit exceeded." Am citit borderoul de evaluare, dar nu am gasit nicaieri "SIGNAL11".Ce inseamna asta?



Apropo, am gandit problema in alt mod fata de cum era prezentata rezolvarea pe site si imi merge. Help me please.

[•devilkind]

Killed by signal 11 e SIGSEGV (despre asta cred ca ar trebui sa gasesti in documentatie). In principiu ai depasit limita de memorie admisa de problema sau accesezi un element care nu exista. De ex ai un vector int a[100] si accesezi elementul a[1000].

Nu e nici o problema daca gasesti o solutie alternativa insa trebuie sa ai grija ca rezolvarea ta sa se incadreze in timp.

[•cosmina_yup]

Eu am pus cam multe for-rui in program, poate fii asta problema? Cum pot reduce timpul de executie?
Am gandit in felul urmator:
-iau toate numerele din intervalul A...B si le pun intr-un vector
-intr-o variabila retin numarul de divizori ai lui A
-in aceeasi variabila adaug nr de divizori ai lui B
-si apoi numarul de divizori ai numerelor din interval (care se afla in vector)

Ideea e ca merge asa cum a zis eu.Am incercat si pentru valori cuprinse intre 3 si 6->>11 

[•toni2007]

Diferenta dintre A si B poate fi destul de mare, deci nu vei lua prea multe puncte asa (nu iti intra nici in timp si nici in memorie, de acolo iei killed by signal 11). Problema are solutie in articolul de solutii de la concursul la care a fost propusa.

[•cosmina_yup]

Din explicatia aceea nu am priceput cine este N si cine este X. 

si un numar X

orice numar X?

I-am dat lungimea vectorului destul de mare (1000)...Incerc sa mai optimizez varianta mea.

[•Abi79]

In solutie scrie ca:  "Astfel se iau toate numerele i de la 1 la sqrt(N) si se vor tine intr-un vector sortate valorile: i si N/i."
Atunci, pentru N=17

sqrt(N) = 4
v_i = N/i

v_i: 17 8 5 4
i:   1  2 3 4

Pana aici inteleg (presupunand ca am facut bine vectorul). Apoi: "Acum pentru doua pozitii consecutive in acest vector vom avea doua valori: X1 si X2 si N/X1 = N/X2".

X2 este egal cu X1+1? (sunt consecutive?)

Cum poate fi N/X1 egal cu N/X2? Pana in sqrt(N) valorile N/X sunt toate diferite, nu?


Edit: Vectorul se face (pe foaie; o sa gasiti o formula care sa nu aiba nevoie de vector) cum am scris mai sus, v_i = N/i, dar trebuie continuat pana la capat. De exemplu, pentru N=11, v={11, 5, 3, 2, 2, 1, 1, 1, 1, 1, 1}.

Observati ca prima fraza din rezolvare e ok (Se afla solutia pentru intervalul [1, A-1] si [1, B] si se face diferenta), si ca pentru intervalul [1, 11] de exemplu, solutia lui ar fi suma elementelor din vector (cum scrie in rezolvare, before it starts saying stuff that makes no sense).

Now that you've done that, faceti vectorul pentru cateva numere (sa zicem 12, 15, 22, 23 si la final 11, care face exceptia de la formula), puneti i-ul sub fiecare element si o sa gasiti formula cu care se aduna toate elementele din vector (cateva elemente se repeta, si daca luam vectorul de la 1 pana la sfarsit, iese din timp). Simple and fun.

[•dornescuvlad]

Solutia se bazeaza pe faptul ca aceste numere se repeta pe anumite intervale. Astfel se iau toate numerele i de la 1 la sqrt(N) si se vor tine intr-un vector sortate valorile: i si N/i. Acum pentru doua pozitii consecutive in acest vector vom avea doua valori: X1 si X2 si N/X1 = N/X2. Si orice numar din intervalul [X1, X2], sa zicem Y va avea N/Y = N/X1. Acum se iau toate pozitiile consecutive in vectorul format si se aduna la solutie (N/X1)*(X2-X1+1) (lungimea intervalului). Corectitudinea acestei solutii se bazeaza pe faptul ca daca ar fi sa imparti numarul N la toate numerele de la 1 la N, se obtin 2*sqrt(N) diferite caturi. De exemplu nu poti sa imparti 12 la ceva mai mic egal cu 12 si sa obtii catul 11. Complexitatea va fi O(sqrt(N)).

Eu am nevoie de N elemente in "vectorul" meu pentru a construi solutia ?
=> ca eu o sa am 2 * sqrt(N) numere cu solutia explicata in articol.
Restul de numere n - 2 * sqrt(n) cum le obtin ?

L.E : De multe ori intampin probleme in intelegerea solutiilor din articolele de pe infoarena.Inteleg ca fiecare lucreaza pt. el, altii nu au timp sa explice mai detaliat solutiile...
Ultima parte nu o inteleg deloc (De ce a scris autorul 4 radnuri in loc sa spuna direct : se insumeaza valorile din vectorul obtinut ?)
Am recitit de multe ori paragraful acesta si mi se pare lipsit de sens. (exact cum spune Aby acum 1 an)
Ar fi bine sa fie verificate articolele inainte de a fi publicate(sau scrise doar de anumite persoane), ca sa inteleaga orice muritor din ce parte bate vantul.

[•edp100]

Eu am citit in clasa a 5-a solutia si am inteles totul perfect.

[•dornescuvlad]

Pai dumneata esti Mihai Eminescu, e normal.
Eu pe clasa a 5-a, coseam iarba.

/*
Ma numesc Dani Posdarascu, am 2 conturi pe infoarena şi sunt mare smecher
*/

FOARTE TRIST!

Poate cineva sa modifice/explice solutia? Multumesc.

[•brucewillis]

daca citesti de 5 ori pe diagonala normal ca nu intelegi. De ce nu abordezi probleme mai simple pe care sa le poti rezolva? Daca nu iti plac articolele de ce nu scrii tu mai bune? Nu cred ca dupa felul in care pui tu problema vei fii ajutat vreodata.

[•dornescuvlad]

Trimbitas Petru, as rescrie articolul daca mi-ar explica cineva cum se rezolva.

[•brucewillis]

cred ca ma confunzi:p

[•toni2007]

Ce de-a nume celebre pe aici... Mihai Eminescu, Bruce Willis, Vlad Dornescu...

[•CezarMocan]

Gata, acum ca v-ati luat de Vlad de pe conturile de surse (si nu numai), comunitatea va va aprecia de 3 ori mai mult  . Serios vorbind, ar fi bine sa incetati, pentru ca cearta asta nu duce nicaieri. In loc sa va bateti capul cu ce mesaj la misto sa postati, ati putea sa ajutati omul sa inteleaga problema, sau sa imbunatatiti explicatia din articol.
E foarte trist ca unii care au ajuns sa se creada "mari bazati" incep sa faca misto in stanga si in dreapta. Stiu ca asta suna ca o chestie spusa de parinti, dar chiar ar trebui sa va revizuiti atitudinea.

[•pauldb]

@Toni:
Si cu tine s-au facut 4.

@Toti \ {Vlad}:
Daca tot sunteti toti atat de isteti, ati putea sa-i explicati omului cum se face problema. In rest a spus Cezar ce era de zis.

@Toti:
Echipa infoarena nu are timp sa slefuiasca fiecare articol in parte. De aceea, de fiecare data cand credeti ca ceva poate fi facut mai bine, puteti chiar voi sa imbunatatiti lucrul respectiv. Infoarena este un wiki tocmai din acest motiv.

@Vlad:
Suma numarului de divizori al tuturor numerelor intre 1 si N = numarul de numere divizibile cu 1 (intre 1 si N) + numarul de numere divizibile cu 2 + numarul de numere divizibile cu 3 + ... +  numarul de numere divizibile cu N, adica rezultatul este suma cu i intre 1 si N din [N/i].

Sa consideram ca N = 16. Avem atunci fiecare termen al sumei este:

1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
16 8  5  4  3  2  2  2  1   1  1   1   1  1   1  1

Se observa (dar se poate demonstra si mai riguros) ca vor fi ~2*sqrt(N) termeni distincti in suma (toti i cu proprietatea ca 1 <= i <= sqrt(N) si corespondentii N/i). In cazul de fata acesti termeni sunt 1, 2, 3, 4, 5, 8 si 16. Fie m numarul de termeni. Atunci orice termen T[j] (1 <= j <= m) apare de T[m-j+1] - T[m-j] ori, din modul in care functioneaza partea intreaga.

[•dornescuvlad]

Multumesc mult, am inteles solutia acum! 
Am sa modific eu articolul cu solutii, daca primesc permisiunea.