Cod sursa(job #174981)

Utilizator valentinroscaRosca Valentin valentinrosca Data 9 aprilie 2008 14:00:13
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.53 kb
//Determinati toate fr.
//ireductibile care au numitorul cel mult n
#include<fstream.h>
#include<math.h>
long n,a,b,ca,cb,i,k,r,n1[1000001],n2[1000001],ok;
int main()
{
ifstream fin("fractii.in");
ofstream fout("fractii.out");
fin>>n;
for(a=1;a<=n;a++)
for(b=1;b<=n;b++)
{
ca=a;
cb=b;
do
{
r=ca%cb;
ca=cb;
cb=r;
}
while(r);
ok=1;
for(i=1;i<k;i++)
if((a/ca==n1[i])&&(b/ca==n2[i]))
ok=0;
if(ok)
{
k++;
n1[k]=a/ca;
n2[k]=b/ca;
}
}
//for(i=1;i<=k;i++)
//fout<<n2[i]<<"/"<<n1[i]<<"  ";
fout<<k;
return 0;
}