|
ditzone
Vizitator
|
 |
« : Octombrie 23, 2005, 21:49:46 » |
|
Aici puteţi discuta despre problema Divizor si multiplu. |
|
|
|
|
Memorat
|
|
|
|
•junior
Strain
Karma: 20
 Deconectat
Mesaje: 42
|
|
« Răspunde #1 : Noiembrie 07, 2005, 21:20:10 » |
|
In ce complexitate se face problema asta? Ca am incercat diverse variante care nu se incadrau in timp...
|
|
|
|
|
Memorat
|
|
|
|
|
•bogdan2412
|
|
« Răspunde #2 : Noiembrie 08, 2005, 18:02:07 » |
|
Eu am O(sqrt(N))
|
|
|
|
|
Memorat
|
|
|
|
|
•Adriana_S
|
|
« Răspunde #3 : Noiembrie 13, 2005, 12:33:48 » |
|
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 |
|
|
|
|
Memorat
|
|
|
|
|
VladS
Vizitator
|
|
« Răspunde #4 : Noiembrie 13, 2005, 13:26:17 » |
|
N e Y/X. E ceva cu divizorii lui Y/X  |
|
|
|
|
Memorat
|
|
|
|
|
•Adriana_S
|
|
« Răspunde #5 : Noiembrie 13, 2005, 13:31:31 » |
|
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. |
|
|
|
|
Memorat
|
|
|
|
|
u-92
Vizitator
|
|
« Răspunde #6 : Noiembrie 13, 2005, 14:37:44 » |
|
nu chiar.. log(n) complexitate logaritmica, n^2 complexitate patratica, sqrt(n) complexitate (cum se zice aici?  ).. oricum, cam asta e ideea |
|
|
|
|
Memorat
|
|
|
|
|
•Adriana_S
|
|
« Răspunde #7 : Noiembrie 13, 2005, 15:16:32 » |
|
atunci, my bad  am zis si eu asa, plina de inocentza si doar cu ganduri de pace  |
|
|
|
|
Memorat
|
|
|
|
|
•vladcyb1
|
|
« Răspunde #8 : Noiembrie 13, 2005, 21:56:28 » |
|
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)  |
|
|
|
|
Memorat
|
Vlad Berteanu
|
|
|
|
•Adriana_S
|
|
« Răspunde #9 : Noiembrie 14, 2005, 12:06:28 » |
|
ma rog, nu mi-a zis mie |
|
|
|
|
Memorat
|
|
|
|
|
•cristy
|
|
« Răspunde #10 : Noiembrie 17, 2005, 16:57:57 » |
|
ce da pt 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... |
|
|
|
|
Memorat
|
... lipsa de inspiratie ...
|
|
|
|
•tm_radu
|
|
« Răspunde #11 : Iulie 09, 2006, 18:54:24 » |
|
Imi zice si mie cineva cat da pe: 5
5 30
2 120
3 630
5 4410
1 9699690
? va rog... |
|
|
|
|
Memorat
|
Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
|
|
|
|
u-92
Vizitator
|
|
« Răspunde #12 : Iulie 10, 2006, 10:26:01 » |
|
|
|
|
|
|
Memorat
|
|
|
|
|
•tm_radu
|
|
« Răspunde #13 : Iulie 11, 2006, 13:53:08 » |
|
daca nu exista solutie ce se va afisa?
|
|
|
|
« Ultima modificare: Noiembrie 19, 2007, 01:17:25 de către Toma Radu »
|
Memorat
|
Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
|
|
|
|
•filipb
|
|
« Răspunde #14 : Iulie 11, 2006, 13:57:54 » |
|
Ce inseamna nu exista solutie? Daca nu va exista nici o pereche (p q) se va afisa 0.
|
|
|
|
|
Memorat
|
|
|
|
|
•DraStiK
|
|
« Răspunde #15 : Februarie 20, 2009, 17:02:50 » |
|
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
|
|
|
|
|
Memorat
|
|
|
|
|
•wefgef
|
|
« Răspunde #16 : Februarie 20, 2009, 17:16:25 » |
|
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: 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);
|
|
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
|
•DraStiK
|
|
« Răspunde #17 : Februarie 20, 2009, 17:20:52 » |
|
multumesc frumos wefgef acuma ar trebui sa o fac  |
|
|
|
|
Memorat
|
|
|
|
•mihaela-roxana
Strain
Karma: 0
Deconectat
Mesaje: 1
|
|
« Răspunde #18 : Noiembrie 03, 2009, 21:01:42 » |
|
Adica daca d(divizorul)D10=1,2,5,10 Nu?  |
|
|
|
|
Memorat
|
|
|
|
|
•SpiderMan
|
|
« Răspunde #19 : Martie 17, 2010, 16:49:03 » |
|
Nu inteleg ce ai scris tu acolo  |
|
|
|
« Ultima modificare: Martie 18, 2010, 15:02:08 de către Simoiu Robert »
|
Memorat
|
|
|
|
•caen1
Client obisnuit
Karma: 22
Deconectat
Mesaje: 75
|
|
« Răspunde #20 : Mai 14, 2011, 17:44:00 » |
|
Nu prea inteleg cum sa fac factorizarea rapida. Imi poate explica/da un link cineva? Multumesc!
|
|
|
|
|
Memorat
|
|
|
|
|
•ctlin04
|
|
« Răspunde #21 : Iulie 13, 2011, 23:39:19 » |
|
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....
|
|
|
|
|
Memorat
|
|
|
|
|
•SpiderMan
|
|
« Răspunde #22 : Iulie 14, 2011, 08:06:38 » |
|
|
|
|
|
|
Memorat
|
|
|
|
|
•ctlin04
|
|
« Răspunde #23 : August 15, 2011, 01:46:12 » |
|
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  |
|
|
|
|
Memorat
|
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #24 : August 15, 2011, 12:28:36 » |
|
Puterea lui 2 ai pus-o longint?
In rest, habar n-am. Poate ne ajuta o sursa.
|
|
|
|
|
Memorat
|
|
|
|
|
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena