Minimum possible sum of array B such that AiBi = AjBj for all 1 â ‰¤ i < j â ‰¤ N | C ++ 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 ( ( a ^ m1 ) % mod ) ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define mod  (int)(1e9 + 7) NEW_LINE #define N  1000005 NEW_LINE int lpf [ N ] ; void least_prime_factor ( ) { for ( int i = 1 ; i < N ; i ++ ) lpf [ i ] = i ; for ( int i = 2 ; i < N ; i ++ ) if ( lpf [ i ] == i ) for ( int j = i * 2 ; j < N ; j += i ) if ( lpf [ j ] == j ) lpf [ j ] = i ; } int power ( int a , int m1 ) { if ( m1 == 0 ) return 1 ; else if ( m1 == 1 ) return a ; else if ( m1 == 2 ) return ( 1LL * a * a ) % mod ; else if ( m1 & 1 ) return ( 1LL * a * power ( power ( a , m1 / 2 ) , 2 ) ) % mod ; else return power ( power ( a , m1 / 2 ) , 2 ) % mod ; } long long sum_of_elements ( int a [ ] , int n ) { least_prime_factor ( ) ; map < int , int > prime_factor ; for ( int i = 0 ; i < n ; i ++ ) { int temp = a [ i ] ; map < int , int > single_number ; while ( temp > 1 ) { int x = lpf [ temp ] ; single_number [ x ] ++ ; temp /= x ; } if ( i == 0 ) prime_factor = single_number ; else { for ( auto x : single_number ) prime_factor [ x . first ] = max ( x . second , prime_factor [ x . first ] ) ; } } long long ans = 0 , lcm = 1 ; for ( auto x : prime_factor ) lcm = ( lcm * power ( x . first , x . second ) ) % mod ; for ( int i = 0 ; i < n ; i ++ ) ans = ( ans + ( lcm * power ( a [ i ] , mod - 2 ) ) % mod ) % mod ; return ans ; } int main ( ) { int a [ ] = { 2 , 3 , 4 } ; int n = sizeof ( a ) / sizeof ( int ) ; cout << sum_of_elements ( a , n ) ; return 0 ; }