Minimize sum of K positive integers with given LCM | C ++ program to implement the above approach ; Function to find the prime power of X ; Stores prime powers of X ; Iterate over the range [ 2 , sqrt ( X ) ] ; If X is divisible by i ; Stores prime power ; Calculate prime power of X ; Update X ; Update p ; Insert prime powers into primePow [ ] ; If X exceeds 1 ; Function to calculate the sum of array elements ; Stores sum of array elements ; Traverse the array ; Update sum ; Function to partition array into K groups such that sum of elements of the K groups is minimum ; If count of prime powers is equal to pos ; Stores minimum sum of of each partition of arr [ ] into K groups ; Traverse the array arr [ ] ; Include primePow [ pos ] into i - th groups ; Update res ; Remove factors [ pos ] from i - th groups ; Utility function to calculate minimum sum of K positive integers whose LCM is X ; Stores all prime powers of X ; Stores count of prime powers ; Stores minimum sum of K positive integers whose LCM is X ; If n is less than or equal to k ; Traverse primePow [ ] array ; Update sum ; Update sum ; arr [ i ] : Stores element in i - th group by partitioning the primePow [ ] array ; Update sum ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > primePower ( int X ) { vector < int > primePow ; for ( int i = 2 ; i * i <= X ; i ++ ) { if ( X % i == 0 ) { int p = 1 ; while ( X % i == 0 ) { X /= i ; p *= i ; } primePow . push_back ( p ) ; } } if ( X > 1 ) { primePow . push_back ( X ) ; } return primePow ; } int getSum ( vector < int > & ar ) { int sum = 0 ; for ( int i : ar ) { sum += i ; } return sum ; } int getMinSum ( int pos , vector < int > & arr , vector < int > & primePow ) { if ( pos == primePow . size ( ) ) { return getSum ( arr ) ; } int res = INT_MAX ; for ( int i = 0 ; i < arr . size ( ) ; i ++ ) { arr [ i ] *= primePow [ pos ] ; res = min ( res , getMinSum ( pos + 1 , arr , primePow ) ) ; arr [ i ] /= primePow [ pos ] ; } return res ; } int minimumSumWithGivenLCM ( int k , int x ) { vector < int > primePow = primePower ( x ) ; int n = primePow . size ( ) ; int sum = 0 ; if ( n <= k ) { for ( int i : primePow ) { sum += i ; } sum += k - n ; } else { vector < int > arr ( k , 1 ) ; sum = getMinSum ( 0 , arr , primePow ) ; } return sum ; } int main ( ) { int k = 3 , x = 210 ; cout << minimumSumWithGivenLCM ( k , x ) ; return 0 ; }