079 Frac

[spx4]

daca se incearca principiul includerii si al excluderii apar
sume de produse care se identifica cu relatiile lui viette.se identifica polinomu
pacolo
si daca n=p1^a1 * p2^a2 *...*pk^ak
atunci numarul de numere cu proprietatea cautata este
phi(n)=n(1-1/p1)(1-1/p2)...(1-1/pk)

probabil ca o abordare buna ar fi folosind stern-brocot tree sau secvente farey

[Editat de bogdan2412: Nu mai posta de 2 ori consecutive.. Use the Edit button! ]

[•amadaeus]

atunci numarul de numere cu proprietatea cautata este
phi(n)=n(1-1/p1)(1-1/p2)...(1-1/pk)

te referi la functia lui Euler phi(N), care returneaza numarul de intregi mai mici ca N si primi cu N.
Problema era sa aflu cate numere mai mici ca x si prime cu n sunt..
Ideea ramane cam aceeasi, numai ca se modifica putin forma finala.

[•anna_bozianu]

Am si eu o nelamurire. Primesc urmatorul mesaj de eroare 

Compilare:
user.cpp: In function 'void solve()':
user.cpp:30: warning: left shift count >= width of type

pentru linia :

left=0;right=1<<61;

(0 puncte cu TLE pe toate testele dar asta se explica de moment ce am un while(right-left-1) si  left=right=0) :

Dupa ce inlocuiesc linia cu :

left=0;right=1;right<<=30;right<<=30;right<<=1;

totul merge perfect (100 puncte ).

Cele doua linii nu ar trebui sa aiba acelasi efect ? ( variabilele left si right sunt de tip long long )

L.E. 10x pauldb

[•pauldb]

Operatia se calculeaza default pe int daca nu ai termeni ai ei long long (valoarea la care se face atribuirea nu conteaza).

left=0;right=1;right<<=30;right<<=30;right<<=1;

Asta poate fi inlocuit cu

Cod:

right = 1LL<<61

[•S7012MY]

Merge cu un euclid+ciur?

[•veleandu]

Tiberiu un ciur pana la 2^60 :-S

nu cred
eu ma gandesc ca .. caut binar rezultatul ( sa il numai X ) ...
X luand valoare intre 0 - 2^61 ..
si pe un X anume calculez cate elemente se impart cu factorii primi ai lui N : ) folosind un pinex "clasic"
daca X- nr care se divid > P .. x scade la jumatate : )

[•pauldb]

Bravo, rezolvarea ta e corecta! Dar nu are rost sa raspunzi la topicuri in care nu s-a mai scris de atata timp.