003 Fractii

[•LucAnd]

am rezolvat problema totu se datora faptului ca nu poti atribiu unei variabile direct un numar mai mare de 32 biti , habar n-aveam de treaba asta , bine ca acuma stiu pe viitor

[•Cosmin]

ba poti si faci asa: x = 1000000000000000L;

[•LucAnd]

Am incercat faza cu 1000000000000L si nu merge

[•Cosmin]

Nu am compilator aici da tre sa mearga, incearca cu ll in coada ... si nu mai astepta mura in gura pt chestii simple, deschide si tu o carte de C/C++ la tipul long long sau manualul cu documentatie sau cauta pe net. Faptul ca ti-am spus ca se poate ar fi trebuit sa te motiveze sa iti pierzi 5 minute cautand o solutie nu sa incerci ce am zis eu, vezi ca nu merge in 10 secunde si esti multumit sa scrii pe forum ca nu ai reusit sa te descurci.

[•spatarel]

Eu fac alfel, si merge intotdeauna

X = (__int64)1000000000 * 1000000000;
sau
X = (long long)1000000000 * 1000000000;
Incearca si:
X = (__int64)1000000000000000000;
sau
X = (long long)1000000000000000000;
dar nu garantez pentru asta.

Tipul folosit difera in functie de compilator
Spor!

[•Coty]

scuze ca intrerup... dar int64 parca este tip cu semn... ia dati un qword in free pascal si aveti un tip fara semn pe 64 de biti care merge pana la 18446744073709551615 (vreo 18.446.744.073 miliarde...) Cred ca  e ceva mai mare...
Bine, nu cred ca ar fi diferenta semnificativa dar...

[•the_godfather]

De ce cand scriu long long si ce vreau sa declar in c++5.02 imi da ceva de tipul too many types in declaration. De ce nu merge?
Si se poate declara ceva de genul int64 n,i,...,a[100] in c++5.02?
sau trebuie sa declar la fiecare variabila in parete x=(long long)100000000000 sau x=(__int64)100000000000000000?

[•svalentin]

scuze, dar eu nu am auzit de c++5.02.... fii si tu mai explicit! C++ este un limbaj; iar versiunea 5.02 de la ce e... ce compilator?! Borland C++ 5.02? Visual Studio C++ 5.02?! GNU C++ 5.02...

[•the_godfather]

Este  versiunea Borland C++ 5.02 dar am uitat sa scriu acest lucru.
Am scris din nou __int64 x si merge, dar acum stiu de ce nu merge long long.Acesta nu merge decat in linux.Am sa scriu sursa cu long si am sa trimit cu long long. Multumesc oricum pentru informatii.

[u-92]

si peste tot unde ai long o sa pui long long? sau eventual bagi un typedef, dar tot trebuie sa modifici la afisare.. e cam complicat

cel mai bine iti compilezi sursele cu gcc.. poti incerca sa folosesti RHIDE, este foarte asemanator cu borlandc, mai multe detalii aici: http://www.delorie.com/djgpp/

[•mist3rfi3ld]

mircea am si eu o intrebare: am o rez in O(n*n)....am auzit ca e prea mare si trebuie in n log n
da da si u o idee  ....pls...nush de unde sa iau log n   . doar in ciurul lui eratostene am cu log n da nush cum mi ar folosi asta aici........

[u-92]

topicul asta are 2 pagini.. daca citesti atent prima o sa gasesti o gramada de indicii.. avand ciurul lui eratostene poti determina pt un numar x, numarul de numere prime cu el mai mici decat el

[•points_hunter]

Nu stiu de ce timpul maxim este 2 secunde la problema asta.
am facut problema asta fara sa trag timpul de par in vr-un fel.
Iata timpiii:::::

Cod:

TEST 1	...[0.05s]...	Ok!
TEST 2	...[0.01s]...	Ok!
TEST 3	...[0.01s]...	Ok!
TEST 4	...[0.01s]...	Ok!
TEST 5	...[0.03s]...	Ok!
TEST 6	...[0.07s]...	Ok!
TEST 7	...[0.15s]...	Ok!
TEST 8	...[0.30s]...	Ok!
TEST 9	...[0.47s]...	Ok!
TEST 10	...[0.65s]...	Ok!

[•devilkind]

pai ce complexitate ai scos?

[•points_hunter]

Aprox. O(n+n*logn). Ceva mai mult.

[•andreisfrent]

Eu nu inteleg ce se intampla la problema asta...
Imi scapa vreun caz particular? (Exista asa ceva?) timpul de executie e bun, 4 teste merg, restul Wrong Answer... imi puteti da si mie un exemplu mai ciudat care sa imi fi scapat?
am rezolvat folosind descompunerea in factori primi a fiecarui numar <n si calculez functia totentiala pentru fiecare si o adun la rezultat... care sa fie problema?

[•filipb]

Vezi k rezultatul tau depaseste int/long, trebuie sa pui long long la toate calculele ( sau int64 in Pascal ). De exemplu pentru 1 000 000 cat iti da?... Ar trebui sa obtii 607927104783...

[vladut.forum]

thanks Cosmin.ro

inca cand eram in ro, incercam la asta cu include si exclude ... da luam niste TLE-uri si m-am lasat...

acum am vazut postu lui Cosmin.ro la top5 probleme, ca a facut cu include si exclude ... si am zis ca sigur mere... daca a facut cineva

asa ca m-am reapucat... si am scoso de 100 

traiasca I/E...

thanks Cosmin.ro again!!

[•k_ounu_eddy]

Am si eu o intrebare.Care este formula generala a functiei totient?O fi asta :
"
By induction, the general case is then
t(n)=n(1-1/(p_1))(1-1/(p_2))...(1-1/(p_r))."
atunci cine sunt p1 p2 ..pr?
De asemenea explicati-mi si mie ce este logaritmul(sunt mai nou in acest domeniu al informaticii).Din cate stiu eu,logaritmul este o putere la care trebuie rdicat un nr,pt a obtine alt numar.Va rog explicati-mi si mie cum pot folosi aceascta proprietate pentru a obtine o complexitate mai mica ,adica n* log n,ca eu am n*n,care am inteles ca e prea mare,si imi iese din timp.De asemenea am mai vazut pe cineva care a scris ca avand ciurul lui Eratostene se poate obtine numarul de numere prime cu n si mai mici decat n.asta nu cumva e la functia totient? Va rog ajutati-ma 

[•devilkind]

p1, p2 .. pr sunt numere prime.

Folosind ciurul lui eratostene poti afla in timp logaritmic numarele prime mai mici decat n.

Vezi ca tot undeva pe acest topic erau niste recurente postate de wickedman, care sunt foarte bune.

PS: poti sa cauti intrun manual de clasa a-X-a de mate despre logaritmi

[•k_ounu_eddy]

Am inteles esenta :cu ciurul lui Eratostene calculezi numerele prime mai mici decat n,iar valorile care le returneaza aceasta functie sunt folosite pentru a calcula tot(n).Dar am o indoiala in privinta functiei totient .De ex sa calculam tot(9):
-numerele prime mai mici decat 9 sunt 2,3,5,7.
-formula generala este tot(n)=n*(1-1/p1)*(1-1/p2)...(1-1/pr).inlocuind numerele obtinem: tot(9)=9*(1-1/2)*(1-1/3)*(1-1/5)*(1-1/7).Facand calculele obtinem rezultatul urmator: 432/210(fractia se mai poate simplifica),dar acest numar nu este intreg,cum se poate asa ceva?.De asemenea ce semnifica pr,cel mai mare numar prim care se afla in intervalul 1,2,3....n?
PS:abia am trecut intr-a 9a,nu am facut nici o ora de info inca,in afara ca ne-am cunoscut profesoru,si stii cum e in prima ora

[•devilkind]

nu e vb de numerele prime mai mici decat n ci de cele care se divid.

Ptr exemplu tau cu 9:
tot(9) = 9*(1-1/3) =  9*(2/3) = 6 (cele 6 numere sunt 1,2, 4,5,7,8)

Succes de aici inainte

[•azotlichid]

Man, just an advice! 

Te sfatuiesc sa nu te apuci de problema asta daca nu stapanesti notiunile de matematica necesare, altfel toata munca ta s-ar reduce efectiv la implementare, ceea ce nu consideram ca are de a face cu Computer Science (scopul spre care se indreapta toate aceste probleme). Pentru cineva care abia a inceput a 9-a este onorabil ca te-ai incumetat la "Fractii"  dar asta presupune inainte si putina cercetare

Iata cateva notiuni de aprofundat si de inteles, necesare acestei probleme:
* numere relativ prime
* factorizarea numerelor naturale
* ciurul lui Erathostene
* formula generala (functia Totient a lui Euler), cand intelegi demonstratia si reusesti sa o refaci singur 
* formula recursiva pentru calculul numarului de numere relativ prime cu un numar dat, mai mici decat acesta
* solutia finala

Spor 

[•pauldb]

Se divid cu cine? 

[cred ca vrei sa spui numerele prime cu N mai mici ca N, ca dupa stiinta mea, toate numerele se divid ]

Pentru eddy: Vezi ca sunt useri pe prima pagina in clasa IX-a, so give us a break.

[•k_ounu_eddy]

La matematica nu am de ce sa imi fac probleme,de fiecare am fost la judeteana la olimpiada(n-am trecut mai departe ce-i drept),dar am luat odata locul 4.In rest ce sa va spun,in C stiu notiunile de baza:variabile,matrici,functii,bactracking,pointeri,am stat mult si am muncit pana acum,toate astea le-am invatat in aprox 2 luni,dar sa nu credeti ca am trecut prin ele ca prin branza,am facut la fiecare exercitii,etc.
PS:PaulDB s-o crezi tu ca toate numerele se divid...de ex ce 4 se divide cu 3?am sa iti dau si definitia matematica:un nr a se divide cu alt nr b daca si numai daca exista un nr c ,astfel incat a=b*c.zi si mie in cazul tau daca a=4, b=3 ,care este c?si mai incetul cu fraze din astea so give us a break.
Pt ceilalti multumesc de ajutor,in special devilkind,si azotlichid.