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
def computeTotient ( N , phi ) : NEW_LINE INDENT for p in range ( 2 , N + 1 ) : NEW_LINE INDENT if phi [ p ] == p : NEW_LINE INDENT phi [ p ] = p - 1 NEW_LINE for i in range ( 2 * p , N + 1 , p ) : NEW_LINE INDENT phi [ i ] = ( phi [ i ] // p ) * ( p - 1 ) NEW_LINE DEDENT DEDENT DEDENT DEDENT def countPairs ( N ) : NEW_LINE INDENT cnt_type1 = 0 NEW_LINE cnt_type2 = 0 NEW_LINE half_N = N // 2 NEW_LINE cnt_type1 = ( half_N * ( half_N - 1 ) ) // 2 NEW_LINE phi = [ 0 for i in range ( N + 1 ) ] NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT phi [ i ] = i NEW_LINE DEDENT computeTotient ( N , phi ) NEW_LINE for i in range ( ( N // 2 ) + 1 , N + 1 ) : NEW_LINE INDENT cnt_type2 += ( i - phi [ i ] - 1 ) NEW_LINE DEDENT print ( cnt_type1 + cnt_type2 ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 6 NEW_LINE countPairs ( N ) NEW_LINE DEDENT