Number of ways to change the Array such that largest element is LCM of array | C ++ implementation to find the Number of ways to change the array such that maximum element of the array is the LCM of the 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 ; Function to find the prefix sum upto the current index ; Function to find the number of ways to change the array such that the LCM of array is maximum element of the array ; Updating BIT with the frequency of elements ; Maximum element in the array ; 1 is for every element is 1 in the array ; ; Vector for storing the factors ; finding factors of i ; Sorting in descending order ; for storing number of indexex 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 ; Loop to find the count which have lcm as i but i is not present ; Adding cnt - toSubtract to answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MOD = 1e9 + 7 ; const int N = 1e5 + 5 ; vector < int > BIT ( N , 0 ) ; int power ( int x , int y ) { if ( x == 0 ) return 0 ; int ans = 1 ; while ( y > 0 ) { if ( y & 1 ) ans = ( 1LL * ans * x ) % MOD ; x = ( 1LL * x * x ) % MOD ; y >>= 1 ; } return ans ; } void updateBIT ( int idx , int val ) { assert ( idx > 0 ) ; while ( idx < N ) { BIT [ idx ] += val ; idx += idx & - idx ; } } int queryBIT ( int idx ) { int ans = 0 ; while ( idx > 0 ) { ans += BIT [ idx ] ; idx -= idx & - idx ; } return ans ; } int numWays ( int arr [ ] , int n ) { int mx = 0 ; for ( int i = 0 ; i < n ; i ++ ) { updateBIT ( arr [ i ] , 1 ) ; mx = max ( mx , arr [ i ] ) ; } int ans = 1 ; for ( int i = 2 ; i <= mx ; i ++ ) { vector < int > factors ; for ( int j = 1 ; j * j <= i ; j ++ ) { if ( i % j == 0 ) { factors . push_back ( j ) ; if ( i / j != j ) factors . push_back ( i / j ) ; } } sort ( factors . rbegin ( ) , factors . rend ( ) ) ; int cnt = 1 ; int prev = 0 ; for ( int j = 0 ; j < factors . size ( ) ; j ++ ) { int remFactors = int ( factors . size ( ) ) - j ; int indexes = n - queryBIT ( factors [ j ] - 1 ) ; cnt = ( 1LL * cnt * power ( remFactors , indexes - prev ) ) % MOD ; prev = max ( prev , indexes ) ; } factors . erase ( factors . begin ( ) ) ; int toSubtract = 1 ; prev = 0 ; for ( int j = 0 ; j < factors . size ( ) ; j ++ ) { int remFactors = int ( factors . size ( ) ) - j ; int indexes = n - queryBIT ( factors [ j ] - 1 ) ; toSubtract = ( 1LL * toSubtract * power ( remFactors , indexes - prev ) ) ; prev = max ( prev , indexes ) ; } ans = ( 1LL * ans + cnt - toSubtract + MOD ) % MOD ; } return ans ; } int main ( ) { int arr [ ] = { 6 , 3 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int ans = numWays ( arr , n ) ; cout << ans << endl ; return 0 ; }