003 Fractii

[•C0Mr4d3]

Imi cer scuze in primul rand ca am raspuns asa de greu
In ceea ce priveste raspunsul cerut, poti sa alegi o valoare pentru n si sa verifici pur si simplu formulele...Nu vad ce alt exemplu as putea sa dau...

Am gandit in felul urmator:

Fractii cu numaratorul par:
1) Stim ca pana la n sunt n div 2 numere pare...
2) Pentru un n par sunt n div 2 fractii cu numaratorul par care se pot simplifica...deci mai raman n - n div 2 care nu se pot simplifica...
din 1 si 2 => (n div 2) * (n - n div 2) fractii cu numarator par care se pot simplifica...

Fractii cu numaratorul impar:
Pentru x care trece prin toate numerele impare de la 3 la n:
1) Sunt n div x fractii care au numaratorul si numitorul divizibile intre ele...raman deci n - n div x care nu se simplifica.
Acest calcul l-am facut in "while".

Mai raman deci doar cateva exceptii...(daca am gandit bine...si e posibil sa fi gresit, nu neg)
Exceptiile sunt de forma: 6/3 6/9 9/3 9/6 10/5

[•SpiderMan]

Incearca sa faci cu metoda asta si vezi ce punctaj iei 

[•pauldb]

Imi cer scuze in primul rand ca am raspuns asa de greu
In ceea ce priveste raspunsul cerut, poti sa alegi o valoare pentru n si sa verifici pur si simplu formulele...Nu vad ce alt exemplu as putea sa dau...

Am gandit in felul urmator:

Fractii cu numaratorul par:
1) Stim ca pana la n sunt n div 2 numere pare...
2) Pentru un n par sunt n div 2 fractii cu numaratorul par care se pot simplifica...deci mai raman n - n div 2 care nu se pot simplifica...
din 1 si 2 => (n div 2) * (n - n div 2) fractii cu numarator par care se pot simplifica...

Fractii cu numaratorul impar:
Pentru x care trece prin toate numerele impare de la 3 la n:
1) Sunt n div x fractii care au numaratorul si numitorul divizibile intre ele...raman deci n - n div x care nu se simplifica.
Acest calcul l-am facut in "while".

Mai raman deci doar cateva exceptii...(daca am gandit bine...si e posibil sa fi gresit, nu neg)
Exceptiile sunt de forma: 6/3 6/9 9/3 9/6 10/5

Nu cred ca vei reusi sa rezolvi problema cu aceasta abordare. Acele fractii pe care le numesti tu exceptii sunt de fapt o multime foarte de mare de fractii. Mai bine incerci alta abordare (pentru indicii poti citi acest topic).

[•C0Mr4d3]

da...intradevar...sunt cam multe "exceptii" mai ales pentru n foarte mare...

[•SpiderMan]

Aceasta problema se rezolva usor cu indicatorul lui Euler, explicat mai bine aici.

[•deiosx]

am o intrebare care s-a pus (presupun) de 1000000 de ori.
Care e metoda Euler?
pls help!!

[•SpiderMan]

am o intrebare care s-a pus (presupun) de 1000000 de ori.
Care e metoda Euler?
pls help!!

Ti-am trimis P.M. , fa ce ti-am zis acolo si e ok

[•RbkPlaY]

auziti.. uitati cum am facut eu

Cod:

#include<fstream>
using namespace std;
int N,P,Q,k;

int cmmdc(int a, int b){
while(a!=0)
{
           int r;
           r=b%a;
           b=a;
           a=r;} return b;}
int main()
{
    ifstream fin("fractii.in");
    ofstream fout("fractii.out");
    fin>>N;
    for(P=1;P<=N;P++)
    for(Q=1;Q<=N;Q++)

    if(cmmdc(P,Q)==1) k++;

    fout<<k;
    return 0;
}

poate sa`mi spuna cineva dc am luat numai 10 puncte?

Editat de admin: Foloseste tagul "code" cand postezi surse.

[•mathboy]

Pentru ca solutia ta nu e eficienta (sunt cateva pagini din acest topic din care ai cateva indicii si ceva de invatat).

[•SpiderMan]

E ineficient, oare de ce? Cauta prin topic Indicatorul lui Euler.
[LE] Am scris in acelasi timp

[•RbkPlaY]

am facut ca acolo... o mers... dar acu am 0 puncte!! dc?

http://infoarena.ro/job_detail/409332?action=view-source

la toate testele zice Killed by signal 11(SIGSEGV).

[•alexandru92]

am facut ca acolo... o mers... dar acu am 0 puncte!! dc?

http://infoarena.ro/job_detail/409332?action=view-source

la toate testele zice Killed by signal 11(SIGSEGV).

pentru ca tu aloci un vector de 0 numere......

[•RbkPlaY]

 ups.. n`am observat.. mc

L. E.: nu e bun? dc? am verificat.. si merge

Editat de admin: Nu posta consecutiv, foloseste butonul "Modifica"

[•alexandru92]

nu e bun? dc? am verificat.. si merge

Scuze, eram cu gandul la altceva ....

[•RbkPlaY]

oricum nu era bun am corectat acuma si am 100 puncte

[•ionut2219]

Nu se vede nimic.

[•deneo]

Ce vrei sa zici cu asta?(nu ai priceput ideea?)

[•sttanciuc]

sirul dat nu trebuia sa fie 1/1 1/2 1/3 1/4 2/1 2/2 2/3 2/4 3/1 3/2 3/3 3/4 1/4 2/4 3/4 4/4? 

[•gabitzish1]

Nu. Sirul este format doar din fractii ireductibile.

[•sttanciuc]

Ce am gresit? De afisat afiseaza bine!

Cod:

#include<fstream>
using namespace std;

int cmmdc(int a, int b)
{
   int x=a, y=b,r;
   while(x%y!=0)
   {
      r=x%y;
      x=y;
      y=r;
   }
   if(r==1)
      return 0;
   else
      return r;
}

int main()
{
   long N;
   int i,j;
   ifstream in("fractii.in");
   ofstream out("fractii.out");
   in>>N;
   int nr=N*N;
   for(i=1;i<=N;i++)
      for(j=1;j<=N;j++)
         if(cmmdc(i,j)!=0&&i!=1&&j!=1)
            nr--;
   out<<nr<<endl;
   out.close();
   in.close();
   return 0;
}

Editat de moderator : Nu mai posta de mai multe ori consecutiv, editeaza-ti posturile anterioare. Foloseste tagurile [ code ] [ /code ] cand postezi cod.

[•gabitzish1]

De afisat afiseaza bine, dar nu afiseaza la timp.
Subiectul problemei are 11 pagini, sigur gasesti indicatii folositoare daca iti faci putin timp sa citesti.

[•uhraurhua]

ma poate ajuta cineva sa-mi dau seama unde am gresit  
plz  

Cod:

#include<iostream.h>
#include<fstream.h>
ifstream fin("fractii.in");
ofstream fout("fractii.out");
void fractii(long long n){
	long long i,s=0;
	for(i=2;i<=n/2;i++)
	s=s+((n/i)-1)*(i+1);
	s=s+n-1;
	s=s-(n/2)+1;
	fout<<n*n-s<<endl;
}
int main(){
long long n;
fin>>n;
fractii(n);
return 0;
}

[•SpiderMan]

Nu e corecta rezolvarea, problema se face cu indicatorul lui euler, si editeaza-ti codul cu tagul code .

[•belicosus]

Editat de admin: Te rog sa folosesti un limbaj civilizat pe forum si sa nu jignesti utilizatorii.

Editat de admin: Te rog sa folosesti un limbaj civilizat pe forum si sa nu jignesti utilizatorii.
De asemenea nu mai posta consecutiv, foloseste butonul "Modifica".

[•SilviuAk]

Din P/Q cu 1 ≤ P,Q ≤ N, se intelege CA : 1<=P si Q<=N

si 1/1 da 1 deci e reductibila si ar afisa doar 10 fractii.