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]: https://www.codechef.com/problems/SNCK04/

[2]: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

[3]: https://en.wikipedia.org/wiki/Euler's_totient_function