003 Fractii

[•SilviuAk]

de ce imi tot spune ca nu aveti pe server fstream.h si iostream.h??

Eu fac programele in Turbo C++ IDE .
Care este problema??

[•xtreme77]

Am si eu o problema:am incarcat sursa asta(http://www.infoarena.ro/job_detail/1107827) acum 2 ore si jumatate si inca nu mi s-a evaluat..in cazul acesta,ce as putea face?

[•spock]

Nu inteleg cum imi iese din timp sursa asta!

Cod:

#include <cstdio>
using namespace std;

int cmmdc(int a,int b){
    if(a==b)
        return a;
    else if(a>b)
        return cmmdc(a-b,b);
    else
        return cmmdc(a,b-a);
}

int main()
{
    freopen("fractii.in","r",stdin);
    freopen("fractii.out","w",stdout);
    register int n,i,j,u;
    u=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if(cmmdc(i,j)==1)
                u++;
        }
    }
    printf("%d",u);
    return 0;
}

[•andreey_047]

Nu inteleg cum imi iese din timp sursa asta!

Cod:

#include <cstdio>
using namespace std;

int cmmdc(int a,int b){
    if(a==b)
        return a;
    else if(a>b)
        return cmmdc(a-b,b);
    else
        return cmmdc(a,b-a);
}

int main()
{
    freopen("fractii.in","r",stdin);
    freopen("fractii.out","w",stdout);
    register int n,i,j,u;
    u=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if(cmmdc(i,j)==1)
                u++;
        }
    }
    printf("%d",u);
    return 0;
}

Tu faci in O(n*n) , n = 1 000 000

[•breahnadavid]

ma ajută și pe mine cineva
de ce nu intru în timp
 
Cod:
#include <iostream>
#include<fstream>
  
  
  
using namespace std;
  
ifstream f;
ofstream g;
  
long int i,j,n;
 
long long t[1000002],k;
  
int main()
{
f.open("fractii.in");
g.open("fractii.out");
  
f>>n;
  
k=0;
for(i=2;i<=n;i++)
        {
        t+=i-1;
        for(j=i+i;j<=n;j+=i)t[j]-=t;
        k+=t;
        }
 
g<<k*2+1;
g.close();
}

... GAtA!!!! am rezolvat problema )))
habar n-aveam ca tipul long long merge mai greu decit int..

[•geaninmihai]

Primesc doar 10 puncte la problema asta, si nu inteleg de ce. Ma poate ajuta cineva?

Cod:

 
#include<fstream>
using namespace std;
int a,b,n;

int cmmdc(int a,int b)
{	while((a!=b)&&(a>0)&&(b>0))
				{if(a>b)a=a-b;
				 else b=b-a;
				}
return a;
}

int main()
{int s=0;
	ifstream f ("fractii.in");
	ofstream g ("fractii.out");
	f>>n;
	f.close();	
	
	for(int i=1;i<=n;i++){
							for(int j=1;j<=n;j++)
								if(cmmdc(i,j)==1)s+=1;
						}
	g<<s;
	g.close();
							
		
return 0;
}

[•SebiSebi]

Programul tau nu este suficient de rapid si de aceia primesti Time Limit Exceeded. Rezolvarea ta nu este cea optima, adica ordinul de complexitate este prea mare. Pentru 100p trebuie sa folosesti indicatorul lui Euler. 

[•cristiandrei]

rezultatele la problema sunt bune dar nu stiu cum sa fac sa pot rula si nr. 1000000?

[•MAlexandru]

mie personal in opinia mea mie nu mi-a placut aceasta problema dupa mine dupa parerea mea

[•MareSite]

O problema frumoasa, dar "catchy" asa

[•Mircea_Donciu]

Fac un ciur care da si indicatorul lui euler pt nr de la 2 la un milion apoi adun totul pana la n, imultesc cu 2 adun 1, imi da la toate testele mele dar pe problema imi da 0. Ati putea sa-mi explicati de ce.

[•liquidsky]

Hei, imi spuneti, va rog, daca e buna rezolvarea asta? (am incercat sa trimit dar nu am nicio sansa  ) multumesc.

[•liquidsky]

#include <iostream>
using namespace std;

bool sunt_prime (int a, int b)
{int r;
while (b!=0)
{r=a%b;
 a=b;
 b=r;
}
 if (a==1)
return true;
else
return false;
}


int main()
{
    int numa, numi,rezult,n;
    rezult=0;
    cin >> n;
    for (numa=1 ; numa<=n; numa++)
    {
        for (numi=1; numi<=n; numi++){
            if (sunt_prime(numa, numi)==true)
                {
                    rezult ++;
            }
        }
    }
    cout << rezult ;

}

[•Elisei1999]

#include <iostream>
#include <fstream>

using namespace std;

int main()
{
    ifstream fin("fractii.in");
    ofstream fout("fractii.out");

    int N, numarator, numitor, i, contor = 0, gasit;
    fin >> N;

    for(numarator = 1; numarator <= N; numarator++){
        for(numitor = 1; numitor <= N; numitor++){
            gasit = 1;
            for(i = 2; i <= numitor; i++){
                if(numarator % i == 0 && numitor % i == 0){
                    gasit = 0;
                    break;
                }
            }
            if(gasit == 1){
            //  fout<<numarator <<"/"<<numitor<<"  ";
                contor++;
            }
        }
    }
    fout<<endl << contor;

    return 0;
}


Ce ar trebuii sa fac sa ma incadrez in timp? Iau 20 p

[•Galatanu_Bogdan]

Dar, 1/1 e ireductibil? Rezultatul e 1.

[•pro119]

Dar, 1/1 e ireductibil? Rezultatul e 1.

1/1 e ireductibil, pentru ca nu poti sa-l mai simplifici, de exemplu 2/2 simplifici prin 2 si primesti 1/1 ... simplificand 1/1 prin 1 tot 1/1 iti da.

[•picah]

ce e gresit??
#include <iostream>
#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("fractii.in");
ofstream fout("fractii.out");
enum{RED,IRED};
int fr_red(int i,int j)
{
    int r;
    do
    {
        r=i%j;
        i=j;
        j=r;
    }while(r);
    if(i==1)
        return IRED;
    return RED;

}
int nr_fractii(int N)
{
    int nr=0;
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
            if(fr_red(i,j)==IRED)
                nr++;


    }
    return nr;
}
int main()
{
    int N;
    fin>>N;
    fout<<nr_fractii(N);
    return 0;

}