003 Fractii

[•skyel]

poate sa imi trim si mie cineva care a facut de 100 exele sa vad mai exact de la ce numar o ia p aratura 
p [email protected]

LE: Nevermind found it(dupa un indelung debug pe fisiere)

[•Qbyx]

Multumesc pentru sfaturi - am reusit si eu! 

[•Florian]

Problema asta e groaznica... :fool:m-am kinuit foarte mult timp la ea...dar in zadar..am citit toate indiciile de pe forum, dar tot nu inteleg cum sta treaba cu ciurul lui eratostene...nu ma prind kum m`ar ajuta generarea numerelor prime pentru cazul in care eu trebuie sa verific dak a si b sunt prime intre ele...pt k asta imi trebuie...si cu brute force (adik cu calcurarea cmmdc-ului la fiecare pas, ceea ce cu siguranta nu e indicat) iese doar 10 puncte

[•dodgerblue]

am citit toate indiciile de pe forum, dar tot nu inteleg cum sta treaba cu ciurul lui eratostene...nu ma prind kum m`ar ajuta generarea numerelor prime pentru cazul in care eu trebuie sa verific dak a si b sunt prime intre ele

citeste despre functia totient in special. aia te ajuta 

[•Florian]

Multumesc pt sfat Bogdan...am inteles ce e aia functie totient,  insa pierd precizie in afisare....adik imi afiseaza cu 1 in plus..sau cu 2 in minus (fata decat ar trebui)...help me careva..pls...


[edit later]....nu.....m-am inselat..din ce am inteles eu, functia totient returneaza toate nr relativ prime cu i , care insa sunt mai mici k i. Dar trebuie sa fac cumva sa-mi returneze nr relativ prime cu i care sunt mai mici sau egale cu n. (unde 1<=i<=n); deci..ar putea cineva sa-mi dea vreun sfat cum as putea sa fac lucrul asta?? pls...multumesc anticipat,,

[•edu2004eu]

Killed by signal 11(SIGSEGV)... asta imi zice la problema Fractii si imi da 10 pct. Ce inseamna signal 11? Mersi!

[•astronomy]

Killed by signal: Cea mai frecventa eroare cand ai un bug in program. Cand un program incalca anumite conventii in UNIX acel program primeste un "semnal" care de cele mai multe ori il opreste. Cateva semnale comune:
    * 11(SIGSEGV): Segmentation fault. Asta in 99% din cazuri inseamna ca ai probleme cu accesul la memorie. Ai iesit din limitele unui vector, ai facut stack overflow, etc.
    * 8(SIGFPE): Floating point error. Cauza cel mai frecvent de impartiri la 0.

[•vanila0406]

eu am incercat cu indicatorul lui euler...however...am dekt 30

[•Bluedrop_demon]

Am folosi ciurul lui eratostene si functia totient, dar imi sare din timp pe 7 teste. Cum se poate face mai optim ?

[•pauldb]

Ai citit articolul? http://infoarena.ro/Ciurul-lui-Erathostene

[•Florian]

Am inteles si functia totient, dar nu pot optimiza ciurul lui eratostene. Iau doar 30 de puncte amarate. Ar putea cineva sa-mi trimita algoritmul cu ciurul optimzat, kre sa poata sa scoata 100?? vreau doar ciurul..fara restul sursei..pls... ](*,)pls...

[•Bluedrop_demon]

Ai citit articolul? http://infoarena.ro/Ciurul-lui-Erathostene

Aici este codul de la ciur optimizat. L-am folosit si eu pe cel mai rapid, dar nu de acolo era problema (cum de altfel ma asteptam) ci de la functia totient, pe care eu o calculez dupa formula, nu reusesc sa gasesc rezolvarea buna pentru a construi un vector cu valorile date de totient in acelasi timp cand fac ciurul.

P.S. la linkul de mai sus gasesti codul in java, dar daca scoti antetul functiilor (specific java) ramane cod C. Iar transformarea (la ultima optimizare) sa nu mai numere valorile prime ci sa le puna intr-un vector creezi un alt vector inlocuind "nr++" cu "vector[2*i+1] = 1" si obtii ciurul.
si mai e o chestie: "vector[2] = 1"

Sper ca nu am scris prostii sau prea explicit. Daca e asa, va rog sa-mi stergeti post-ul.

[•sir_icemaster]

daca vrei sa folosesti functia totient si sa optimizezi timpul de executie te poti folosi de urmatoarele egalitati:

t(p^e) = (p - 1) * p^(e - 1), p numar prim (din definitie)
si
daca p numar prim, p NU divide a,
t(p^e * a) = t(p^e) * t(a) = (p - 1) * p^(e - 1) * t(a)

deci, daca la un moment dat stii t(1), t(2) ... t(n) poti calcula t(n + 1) gasind un singur divizor prim al lui n + 1

Indiciul e mai mult decat suficient pentru rezolvare! De fapt, textul problemei se poate reduce la:
determinati phi(i) pentru i = 2 pana la 1000000.
WM, you are great!

[•vicenzo_cnu]

Te chinui putin la problema asta pana o faci, la fel imi dadea la 7 teste TLE,asa k am optimizat  luand fiecare numar prim si folosind functia totient pt toate numerel divizibile cu el...intra lejer in timp si iei 100 pct

[•maria_p]

am citit tot topicul...am facut problema, dar pt 1000000imi ruleaza f mult(vreo 2 min cel putin)...am luat 30 de pcte, restu TLE...ma ajuta si pe mine cineva s-o optimizez ca nu stiu cum...pls...
ms anticipat!
LE:nu vad la ce imi folosesc relatiile date de Cristian George Strat...

[•skyel]

cu respectivele formule se gaseste rezultatul ca sa iti intre in timp...o explicatie mai amanuntita gasesti la http://mathworld.wolfram.com/TotientFunction.html

[•Florian]

Ei bine..am inteles ciurul...si am reusit sa fac de 100! 10x Gheorge Guraliuc..cu indiciul tau am reusit, insa si cu ajutorul celor care au postat informatii referitoare la functia totient!! Multumesc!

[•gabitzish1]

    phi(n)=(p₁-1)p₁^k₁-1 ... (p_r-1)p_r^k_r-1
E buna formula pt functia totient?

[•adrianradulea]

    phi(n)=(p₁-1)p₁^k₁-1 ... (p_r-1)p_r^k_r-1
E buna formula pt functia totient?

Formula pentru functia totient e foarte buna 

[•gabitzish1]

  Merci pt raspuns a trecut mult de cand am pus intrebarea respectiva
Am facut problema pana la urma  chiar era buna formula ...

[•mordred]

asta e formula, mai usor de inteles si/sau folosit 
exemplu:


edit:
1. oops, nu am vazut ca a mai fost postata formula asta...
2.imi da raspuns gresit 7/10, de la tipurile de int, dar nu`mi dau seama ce poate avea... timp oriqm scot<0,3s si pt valori mici merge bine 

re-edit: am rezolvat  uitasem sa pun long long undeva

[•fireatmyself]

incearca ca rezultatul pe care-l calculezi sa-l memorezi intr-o variabila de tip "long long", iar cand vrei sa adaugi o valoare care are timp intreg faci conversie de tip pentru acea variabila:

Cod:

long long rez;
int a = 100;
rez += (long long)a;
printf("%lld\n", rez);

in rest eu am folosit tipul "double" pentru a lucra cu numere reale.

[•BigMazilu]

Am si eu o intrebare..cu ce invat la scoala pot sa fac problema asta???
Sau trebuie sa mai invatz pe langa ce se preda la scoala (sunt la profil mate-info) ca sa inteleg si eu ceva.. Sunt clasa a 11-a,  am 17 ani, si n-am auzit de ciurul lui eratostene si nici de functia totient...si ce-i aia complexiatate doamne fereste, nu mai inteleg nimik...dar programarea este viata mea..si nu ma voi lasa...va rog frumos ajutati-ma..!!

[•cos_min]

Am si eu o intrebare..cu ce invat la scoala pot sa fac problema asta???
Sau trebuie sa mai invatz pe langa ce se preda la scoala (sunt la profil mate-info) ca sa inteleg si eu ceva.. Sunt clasa a 11-a,  am 17 ani, si n-am auzit de ciurul lui eratostene si nici de functia totient...si ce-i aia complexiatate doamne fereste, nu mai inteleg nimik...dar programarea este viata mea..si nu ma voi lasa...va rog frumos ajutati-ma..!!

Ah se pare ca trebuie sa inveti si din alte surse decat cele de la scoala. Am impresia ca la scoala ta nu se fac prea multe. Despre complexitate s-a mai vorbit pe forum, da-i un search. Legat de ciur ai mai multe informatii aici : http://infoarena.ro/Ciurul-lui-Erathostene.

[•wefgef]

http://infoarena.ro/forum/index.php?topic=2512.0

Poate te ajuta.