# SNCK04 - Unofficial Editorial

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;

}

``````
2 Likes

Thanks a lot for this editorial. Since I’m just a school level student I had no idea about the Phi function and how to approach a question like this, besides brute forcing it by seeing which pairs had gcd(1).

//