Number of ways to change the Array such that largest element is LCM of array | Modulo ; Fenwick tree to find number of indexes greater than x ; Function to compute x ^ y % MOD ; Loop to compute the x ^ y % MOD ; Function to update the Binary Indexed Tree ; Loop to update the BIT ; Function to find prefix sum upto idx ; Function to find number of ways to change the array such that MAX of array is same as LCM ; Updating BIT with the frequency of elements ; Maximum element in the array ; For storing factors of i ; Finding factors of i ; Sorting in descending order ; For storing ans ; For storing number of indexes greater than the i - 1 element ; Number of remaining factors ; Number of indexes in the array with element factor [ j ] and above ; Multiplying count with remFcators ^ ( indexes - prev ) ; Remove those counts which have lcm as i but i is not present ; Adding cnt - toSubtract to ans ; ; Driver Code
MOD = int ( 1e9 ) + 9 NEW_LINE MAXN = int ( 1e5 ) + 5 NEW_LINE BIT = [ 0 for _ in range ( MAXN ) ] NEW_LINE def power ( x , y ) : NEW_LINE INDENT if x == 0 : NEW_LINE INDENT return 0 NEW_LINE DEDENT ans = 1 NEW_LINE while y > 0 : NEW_LINE INDENT if y % 2 == 1 : NEW_LINE INDENT ans = ( ans * x ) % MOD NEW_LINE DEDENT x = ( x * x ) % MOD NEW_LINE y = y // 2 NEW_LINE DEDENT return ans NEW_LINE DEDENT def updateBIT ( idx , val ) : NEW_LINE INDENT while idx < MAXN : NEW_LINE INDENT BIT [ idx ] += val NEW_LINE idx += idx & ( - idx ) NEW_LINE DEDENT DEDENT def queryBIT ( idx ) : NEW_LINE INDENT ans = 0 NEW_LINE while idx > 0 : NEW_LINE INDENT ans += BIT [ idx ] NEW_LINE idx -= idx & ( - idx ) NEW_LINE DEDENT return ans NEW_LINE DEDENT def numWays ( arr ) : NEW_LINE INDENT mx = 0 NEW_LINE for i in arr : NEW_LINE INDENT updateBIT ( i , 1 ) NEW_LINE mx = max ( mx , i ) NEW_LINE DEDENT ans = 1 NEW_LINE for i in range ( 2 , mx + 1 ) : NEW_LINE INDENT factors = [ ] NEW_LINE for j in range ( 1 , i + 1 ) : NEW_LINE INDENT if j * j > i : NEW_LINE INDENT break NEW_LINE DEDENT if i % j == 0 : NEW_LINE INDENT factors . append ( j ) NEW_LINE if i // j != j : NEW_LINE INDENT factors . append ( i // j ) NEW_LINE DEDENT DEDENT DEDENT factors . sort ( ) NEW_LINE factors . reverse ( ) NEW_LINE cnt = 1 NEW_LINE prev = 0 NEW_LINE for j in range ( len ( factors ) ) : NEW_LINE INDENT remFactors = len ( factors ) - j NEW_LINE indexes = len ( arr ) - queryBIT ( factors [ j ] - 1 ) NEW_LINE cnt = ( cnt * power ( remFactors ,   \ indexes - prev ) ) % MOD NEW_LINE prev = max ( prev , indexes ) NEW_LINE DEDENT factors . remove ( factors [ 0 ] ) NEW_LINE toSubtract = 1 NEW_LINE prev = 0 NEW_LINE for j in range ( len ( factors ) ) : NEW_LINE INDENT remFactors = len ( factors ) - j NEW_LINE indexes = len ( arr ) - queryBIT ( factors [ j ] - 1 ) NEW_LINE toSubtract = ( toSubtract * power ( remFactors , indexes - prev ) ) NEW_LINE prev = max ( prev , indexes ) NEW_LINE DEDENT ans = ( ans + cnt - toSubtract + MOD ) % MOD ; NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 4 , 3 , 2 ] NEW_LINE ans = numWays ( arr ) ; NEW_LINE print ( ans ) NEW_LINE DEDENT