124 Divizor si multiplu

[ditzone]

Aici puteţi discuta despre problema Divizor si multiplu.

[•junior]

In ce complexitate se face problema asta? Ca am incercat diverse variante care nu se incadrau in timp...

[•bogdan2412]

Eu am O(sqrt(N))

[•Adriana_S]

Eu am O(sqrt(N))

  cine e N? in problema citesti un x, un y, tre sa afisezi un p, un q dar....nimic de N

[VladS]

N e Y/X.  E ceva cu divizorii lui Y/X  

[•Adriana_S]

vai, iti multumesc m-am prins si io din moment ce cmmmc(a,b) = a *b/cmmdc(a,b). numai ca nu ti se pare ciudat sa zici O(sqrt(N)) cand in problema nu exista N? la asta ma refeream.

[u-92]

nu chiar.. log(n) complexitate logaritmica, n^2 complexitate patratica, sqrt(n)
complexitate (cum se zice aici? ).. oricum, cam asta e ideea

[•Adriana_S]

atunci, my bad am zis si eu asa, plina de inocentza si doar cu ganduri de pace

[•vladcyb1]

In momentul in care iti zice O(sqrt(y/x)) ti se sugereaza si o rezolvare...si daia cred ca bogdan ti a zis sqrt(n)  

[•Adriana_S]

ma rog, nu mi-a zis mie

[•cristy]

ce da pt

Cod:

2
2 4219164
3 4

si inca ceva...solutia...se incadreaza in 2^31?....

never mind...e bine...gresala era alta...si...dupa niste calcule am aflat ca rezultatul se incadreaza in 2^31...

[•tm_radu]

Imi zice si mie cineva cat da pe:

Cod:

5
5 30
2 120
3 630
5 4410
1 9699690

? va rog...

[u-92]

Cod:

4
8
16
8
256

[•tm_radu]

daca nu exista solutie ce se va afisa?

[•filipb]

Ce inseamna nu exista solutie? Daca nu va exista nici o pereche (p q) se va afisa 0.

[•DraStiK]

ma ajuta cineva si pe mine: am incercat sa fac ca in articolul cu solutii, dar nu stiu o metoda eficienta de a afla toti divizorii lui y/x in timp rapid.

Multumesc anticipat

[•wefgef]

O(sqrt(N)) e destul de bine?

Daca N se divide cu x atunci putem scrie N = x * y. Observam ca nu putem avea simultan x > sqrt(N) si y > sqrt(N). De aici rezulta codul:

Cod:

int i;
for (i = 1; i * i < N; ++i)
    if (N % i == 0)
        printf("%d\n%d\n", i, N/i);
if (i * i == N)
    printf("%d\n", i);

[•DraStiK]

multumesc frumos wefgef
acuma ar trebui sa o fac

[•mihaela-roxana]

Adica daca d(divizorul)D10=1,2,5,10 


Nu?

[•SpiderMan]

Nu inteleg ce ai scris tu acolo 

[•caen1]

Nu prea inteleg cum sa fac factorizarea rapida. Imi poate explica/da un link cineva? Multumesc!

[•ctlin04]

Nu stiu unde pot vedea articolul cu solutii, dar poate cineva sa-mi dea si mie un hint, care e faza cu divizorii lui y/x?
Poate macar un link ceva....

[•SpiderMan]

http://infoarena.ro/happy-coding-2005-2/solutii

[•ctlin04]

Chiar nu inteleg de ce iau incorect la problema asta, fac exact ca in articol, aflu toti divizorii lui y/x daca y se imarte exact la x, numaru determinat fiind nr=D "din articol", daca y nu se imparte exact la x atunci tiparesc 0, nu stiu ce pot sa mai fac, pe testele mele merge bine, pe testul exemplu si pe cel din comentarii la fel merge bine dar oricum WA 

[•PlayLikeNeverB4]

Puterea lui 2 ai pus-o longint?
In rest, habar n-am. Poate ne ajuta o sursa.