079 Frac

[•domino]

Aici puteţi discuta despre problema Frac.

[•ldoc]

Imi poate da cineva o idee la problema asta, io am incercat cu cmmdc si iau 20 de puncte cu TLE pe celelalte.
am cautat pe internet shi nu am gasit nimic mai rapid ,desi e cam greu cand nu stiu ce sa caut    

[•filipb]

Hint: cautare binara

[•ldoc]

Mai ce promt esti
Nu ma asteptam asa de repede la un raspuns.
Multam de idee cine stie poate o sa iau si eu 100 p in cele din urma

[•Adriana_S]

Care-i complexitatea oficiala?  

[u-92]

probabil n*log(n)

[•filipb]

Nu.. Nu e N log N... Complexitatea e un pic mai "ciudata"...

[•ldoc]

Desi pare cam prosteasca intrebare o sa o pun sa nu mor prost
ce trebuie cautat binar ca eu tot nu m-am prins
intre timp am gasit o rezolvare de 60p cu ajutorul unor obs matematice
dar ce trebuie sa fac sa iau shi eu 100 la pb asta ca ma dispera deja

[•filipb]

Trebuie sa cauti binar rezultatul, ce altceva?... Oricum, pot sa te intreb ce observatie matematica ai gasit?

[•ldoc]

1. am observat ca toate numerele prime cu n mai mari ca n sunt au forma
NrPrimcun[i+n]=NrPrimcun+n
2. am observat ca exista o simetrie intre nr prime cu n mai mici ca n (lucru care reduce cautarea la jumatate)
 Si am folosit un algoritm asemanator cu Ciurul lui Eratostene si descompunera in factori primi a lui n pentru a gasi nr prime cu n.

[•cristy]

e destul de logica observatia ta...

[u-92]

alt hint: de fapt, m-am gandit mai bine si l-am scos ca ar deveni poate prea evident

[BloodyDemon]

Folosesc unsigned long long si iau doar 80 de p.   Long long n-ar trebui sa mearga, nu e pe 64 biti?
Am tot incercat sa schimb pe double, dar asa nu merge descompunerea in factori primi...mai exact operatia modulo.
Corect me if I'm wrong.
Voi cum ati facut?
 

[u-92]

daca ai rezolvat corect, ar trebui sa mearga cu long long fara nici o problema

[BloodyDemon]

cred ca am rezolvat-o corect, din moment ce am luat 80 p.
Folosesc long long...nici nu-mi citeste numarul pe cel mai rau caz: 12000000000.  :cry:
 

[u-92]

daca nu ai luat 100 sigur nu ai rezolvat-o corect
cum citesti un long long?
eu am folosit

Cod:

scanf("%lld\n", &x)

si a mers.

[•filipb]

cred ca am rezolvat-o corect, din moment ce am luat 80 p.
Folosesc long long...nici nu-mi citeste numarul pe cel mai rau caz: 12000000000.  :cry:
 

Ba ti-l citeste, daca citesti de exemplu scanf("%lld", &N). Cred ca tu totusi folosesti Borland, de aia nu poti vedea pe calculatorul tau daca citeste bine sau nu. Lasa long long indiferent daca esti in Borland, ca pe site oricum nu apare problema asta din moment ce se foloseste alt compilator. Oricum, mai trimite solutii in continuare poate iei 100

[BloodyDemon]

Finally...dupa 3 zile si 3 nopti de chiiin...100 puncte. la toate.

Folosesc Dev-Cpp. Citesc cu streamuri... Problema era aceasta:

Cod:

long long st = 1, dr = 100000000000000.0, mij;

Daca scriu simplu dr = 100000000000000; da eroarea : integer constant is too large for 'long' type...deci am scapat cu un warning...

Felicitari pt problema, filipb.  
Mersi de ajutor, u-92.
 

[•Cosmin]

Daca pui x = 100..0L nu merge?

[BloodyDemon]

Pe Dev-Cpp nu merge. In schimb, pe BorlandC merg toate variantele : 10...0, 100...0.0 si 100...0L.
 

[u-92]

nu te baza pe long long in borlandc, ca nu este

[•amadaeus]

cum se poate raspunde eficient la o intrebare de tipul "cate numere mai mici decat x sunt prime cu y?" (preferabil fara a-l factoriza pe y)  

[u-92]

cam trebuie sa folosesti principiul includerii si excluderii.. altfel nu prea vad cum poti rezolva problema

[•amadaeus]

cam trebuie sa folosesti principiul includerii si excluderii.. altfel nu prea vad cum poti rezolva problema

exact la asta ma refeream
inseamna ca solutia ar fi sa il factorizez pe n si pentru o intrebare de tipul "cate numere mai mici ca x si prime cu n sunt?" sa aplic includere/excludere pentru toti factorii primi obtinuti. numai ca apar s-ar putea sa apara prea multi factori primi in descompunerea lui n, si atunci aplicarea pricipiului includerii si excluderii e destul de  

[u-92]

prea multi nu o sa apara gandeste-te putin si o sa-ti dai seama de ce