Cod sursa(job #444361)
#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 = (int*)malloc( (n*n+1) * sizeof(int));
int *nm = (int*)malloc( (n*n+1) * sizeof(int));
int *val = (int*)malloc( (n*n+1) * sizeof(int));
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;
fout<<count;
fin.close();
fout.close();
return 0;
}