okay , this is unofficial editorial to [Rational Numbers (SNCK04)][1] :
PREREQUISITES : [SIEVE OF ERATOSTHENES][2] , [PHI FUNCTION][3]
Problem Statement :
Given ‘n’ , we have to find NUMBER of rational numbers of form P/Q which are smaller than 1 such that P<=n and Q<=n.
( Note : 2/4 and 1/2 are same and cannot be counted twice. Similarly, 1/3 = 3/9 and so on …)
Example :
Suppose , we have n = 4 . So how many of such P/Q can exist ?
case 1 : Q = 4
Then p = 1,2,3 . Note: p cannot be 4 as then P/Q would be 1.
Case 2: Q = 3
Then p can take value 1,2 .
Case 3 : Q = 2
Now p can take value 1. But note that we considered P=2 , Q=4 . So P/Q = 2/4 = 1/2 . So now We cannot consider P=1.
Case 4: Q=1
Now p cannot take any value as P/Q should be < 1 .This would be true for any given n.
So , ans = 5 .
So, How to solve it ?
The idea is simple :
For Q = 2 to n
For P = 1 to Q-1
count such P/Q making sure they are somehow not counted before.
By counted before , i mean first you counted 2/4 but then dont count 1/2 in case of n=4.
So , how to to know if i have counted before or not ?
One simple is idea is only count P/Q whose gcd(P,Q)=1. This will definitely count all P/Q and only once as any rational number has a form P/Q where gcd(P,Q)=1. ex: 2/4 has form 1/2 , 1/5 has form 1/5 etc.
So, our algo becomes :
For Q = 2 to n
For P = 1 to Q-1
if(gcd(P,Q)==1)
count= count+1;
Well , this will cause TLE . So , we optimise a bit more :
I assume from here on that you know euler phi function , how to calculate it and how to implement sieve of eratosthenes.We will be precomputing answer for every n (1<= n <= 1000000) and saving it.
So, for any n , answer is actually : phi(n) + phi(n-1) + … + phi(2)
Step 1: Take an array say composite where you mark 0 if number prime or else 1 if it is composite. Size = 1000001 . [ index = 0 to 1000000]. Initially all are 0.
Step 2: Take another array phi which will store values of phi value of each index .
Step 3: Now , since phi[i]= (phi[i]/prime)*(prime-1) for each prime which divides i .This has to implemented while executing sieve of eratosthenes . Look Below :
for(i=0;i<1000001;++i)//Initialization
{
phi[i]=i;
composite[i]=0;
}
for(i=2;i<1000001;++i) // Implementation Of Sieve of eratosthenes + Phi logic
{
if(composite[i]==0)
{
phi[i]= i-1;
for(j=2*i;j<1000001;j=j+i)
{
composite[j]=1;
phi[j]= (phi[j]/i)*(i-1);
}
}
}
But phi[i] stores only count of numbers which are co prime to i. But When some ‘i’ is given we need to give answer phi[i] + phi[i-1] + phi[i-2] +… + phi[ 2].
So , we do like this instead of adding every time some ‘i’ is asked :
phi[0]=phi[1]=0;
for(i=3;i<1000001;++i)
phi[i]=phi[i-1]+phi[i];
This sum will be greater than 2^32 in some cases . So ,use appropriate data type. Below is complete implementation of solution in c :
#include<stdio.h>
long long phi[1000001],composite[1000001];
int main()
{
int i,j;
for(i=0;i<1000001;++i)
phi[i]=i;
for(i=2;i<1000001;++i)
{
if(composite[i]==0)
{
phi[i]= i-1;
for(j=2*i;j<1000001;j=j+i)
{
composite[j]=1;
phi[j]= (phi[j]/i)*(i-1);
}
}
}
phi[0]=phi[1]=0;
for(i=3;i<1000001;++i)
phi[i]=phi[i-1]+phi[i];
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%lld\n",phi[n]);
}
return 0;
}
Hope That helps … 
[1]: SNCK04 Problem - CodeChef
[2]: Sieve of Eratosthenes - Wikipedia
[3]: Euler's totient function - Wikipedia
