Cod sursa(job #444358)

Utilizator danvlnDan Vln danvln Data 20 aprilie 2010 08:55:01
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <iostream>
#include <fstream>
using namespace std;


int cmmdc(long a, long b)
{
	if(b==0 || a==0)
		return 0;
	long c;
	while(b)
	{
		c = a%b;
		a = b;
		b = c;
	}
	return a==1?0:a;
}

int main()
{
	int n;

	ifstream fin("fractii.in");
	ofstream fout("fractii.out",ios::out);

	fin>>n;
	
	int count=0;

    int nr[101], nm[101], val[101];
     
    for(int i=1;i<=n;i++)
    {
        nr[i] = 1;
        nm[i] = i;
        val[i] = 0;
    }

    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            nr[n * (i-1) + j ] = i;
            nm[n * (i-1) + j ] = j;
            val[n * (i-1) + j ] = 0;        
            //cout<<i<<"/"<<j<<"    ";
        }
        //cout<<endl;
    }

    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=n*n;j++)
        {
            if ( nr[j]*i<=n  && nm[j]*i<=n)
            {
                int k = nr[j]*(i-1) * n + nm[j]*(i-1);
                val[k] = 1;
            }
        }
    }

    count = 0;
    for(int j=1;j<=n*n;j++)
    {
        if(val[j]==0)
        {
            //cout<<nr[j]<<"/"<<nm[j]<<endl;
            count++;
        }
    }
	cout<<count;
	


 //   for(int i=2;i<=n;i++)
 //   {
 //       for(int j=1;j<=n;j++)
 //       {
 //           // both odd
 //           if( (i & 0x1) == 0 && 
 //               (j & 0x1) == 0)
 //           {
 //               continue;
 //           }
 //           
 //           if(j%i != 0 &&  i%j !=0)
 //           {
 //               if(cmmdc(i,j) ==0)
 //               {
 //                   count ++;
 //                   //cout<<i<<"/"<<j<<"    ";
 //               }
 //           }
 //       }
 //       //cout<<endl;
 //   }

	//count += n + (n-1);
	//
	//cout<<count;

	fout<<count;

	fin.close();
	fout.close();

	return 0;
}