human
Count number of pairs ( i , j ) up to N that can be made equal on multiplying with a pair from the range [ 1 , N / 2 ] | Function to compute totient of all numbers smaller than or equal to N.
Iterate over the range [ 2 , N ].
If phi [ p ] is not computed already then p is prime.
Phi of a prime number p is ( p - 1 ).
Update phi values of all multiples of p.
Add contribution of p to its multiple i by multiplying with ( 1 - 1 / p ).
Function to count the pairs ( i , j ) from the range [ 1 , N ] , satisfying the given condition.
Stores the counts of first and second type of pairs respectively.
Count of first type of pairs.
Stores the phi or totient values.
Calculate the Phi values.
Iterate over the range [ N / 2 + 1 , N ].
Update the value of cnt_type2.
Print the total count.
Driver Code"
Solution in Python:
assistant
#Here is code to count number of pairs ( i , j ) up to N that can be made equal on multiplying with a pair from the range [ 1 , N / 2 ] and the other steps required.
 def computeTotient ( N , phi ) :
	for p in range ( 2 , N + 1 ) :
		if phi [ p ] == p :
			phi [ p ] = p - 1
			for i in range ( 2 * p , N + 1 , p ) :
				phi [ i ] = ( phi [ i ] // p ) * ( p - 1 )
def countPairs ( N ) :
	cnt_type1 = 0
	cnt_type2 = 0
	half_N = N // 2
	cnt_type1 = ( half_N * ( half_N - 1 ) ) // 2
	phi = [ 0 for i in range ( N + 1 ) ]
	for i in range ( 1 , N + 1 ) :
		phi [ i ] = i
	computeTotient ( N , phi )
	for i in range ( ( N // 2 ) + 1 , N + 1 ) :
		cnt_type2 += ( i - phi [ i ] - 1 )
	print ( cnt_type1 + cnt_type2 )
if __name__ == ' _ _ main _ _ ' :
	N = 6
	countPairs ( N )