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;
    
    	
    }


Hope That helps … :slight_smile:
[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

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). :stuck_out_tongue: