Minimum possible sum of array B such that AiBi = AjBj for all 1 â ‰¤ i < j â ‰¤ N | Python3 implementation of the approach ; To store least prime factors of all the numbers ; Function to find the least prime factor of all the numbers ; Function to return the sum of elements of array B ; Find the prime factors of all the numbers ; To store each prime count in lcm ; Current number ; Map to store the prime count of a single number ; Basic way to calculate all prime factors ; If it is the first number in the array ; Take the maximum count of prime in a number ; Calculate lcm of given array ; Calculate sum of elements of array B ; Driver code
mod = 10 ** 9 + 7 NEW_LINE N = 1000005 NEW_LINE lpf = [ 0 for i in range ( N ) ] NEW_LINE def least_prime_factor ( ) : NEW_LINE INDENT for i in range ( 1 , N ) : NEW_LINE INDENT lpf [ i ] = i NEW_LINE DEDENT for i in range ( 2 , N ) : NEW_LINE INDENT if ( lpf [ i ] == i ) : NEW_LINE INDENT for j in range ( i * 2 , N , i ) : NEW_LINE INDENT if ( lpf [ j ] == j ) : NEW_LINE INDENT lpf [ j ] = i NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT def sum_of_elements ( a , n ) : NEW_LINE INDENT least_prime_factor ( ) NEW_LINE prime_factor = dict ( ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT temp = a [ i ] NEW_LINE single_number = dict ( ) NEW_LINE while ( temp > 1 ) : NEW_LINE INDENT x = lpf [ temp ] NEW_LINE single_number [ x ] = single_number . get ( x , 0 ) + 1 NEW_LINE temp //= x NEW_LINE DEDENT if ( i == 0 ) : NEW_LINE INDENT prime_factor = single_number NEW_LINE DEDENT else : NEW_LINE INDENT for x in single_number : NEW_LINE INDENT if x in prime_factor : NEW_LINE INDENT prime_factor [ x ] = max ( prime_factor [ x ] , single_number [ x ] ) NEW_LINE DEDENT else : NEW_LINE INDENT prime_factor [ x ] = single_number [ x ] NEW_LINE DEDENT DEDENT DEDENT DEDENT ans , lcm = 0 , 1 NEW_LINE for x in prime_factor : NEW_LINE INDENT lcm = ( lcm * pow ( x , prime_factor [ x ] , mod ) ) % mod NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT ans = ( ans + ( lcm * pow ( a [ i ] , mod - 2 , mod ) ) % mod ) % mod NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT a = [ 2 , 3 , 4 ] NEW_LINE n = len ( a ) NEW_LINE print ( sum_of_elements ( a , n ) ) NEW_LINE DEDENT