Count pairs whose product modulo 10 ^ 9 + 7 is equal to 1 | Python3 program to implement the above approach ; Iterative Function to calculate ( x ^ y ) % MOD ; Initialize result ; Update x if it exceeds MOD ; If x is divisible by MOD ; If y is odd ; Multiply x with res ; y must be even now ; Function to count number of pairs whose product modulo 1000000007 is 1 ; Stores the count of desired pairs ; Stores the frequencies of each array element ; Traverse the array and update frequencies in hash ; Calculate modular inverse of arr [ i ] under modulo 1000000007 ; Update desired count of pairs ; If arr [ i ] and its modular inverse is equal under modulo MOD ; Updating count of desired pairs ; Return the final count ; Driver code
from collections import defaultdict NEW_LINE MOD = 1000000007 NEW_LINE def modPower ( x , y ) : NEW_LINE INDENT res = 1 NEW_LINE x = x % MOD NEW_LINE if ( x == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT while ( y > 0 ) : NEW_LINE INDENT if ( y & 1 ) : NEW_LINE INDENT res = ( res * x ) % MOD NEW_LINE DEDENT y = y // 2 NEW_LINE x = ( x * x ) % MOD NEW_LINE DEDENT return res NEW_LINE DEDENT def countPairs ( arr , N ) : NEW_LINE INDENT pairCount = 0 NEW_LINE hash1 = defaultdict ( int ) NEW_LINE for i in range ( N ) : NEW_LINE INDENT hash1 [ arr [ i ] ] += 1 NEW_LINE DEDENT for i in range ( N ) : NEW_LINE INDENT modularInverse = modPower ( arr [ i ] , MOD - 2 ) NEW_LINE pairCount += hash1 [ modularInverse ] NEW_LINE if ( arr [ i ] == modularInverse ) : NEW_LINE INDENT pairCount -= 1 NEW_LINE DEDENT DEDENT return pairCount // 2 NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 2 , 236426 , 280311812 , 500000004 ] NEW_LINE N = len ( arr ) NEW_LINE print ( countPairs ( arr , N ) ) NEW_LINE DEDENT