LCM#135
The problem asks us to find the Least Common Multiple (LCM) of an array containing integers. Although the values of the array elements are relatively small (a_i \le 100), their cumulative LCM can grow exponentially and easily exceed the capacity of standard data types (like long long in C++). Therefore, we need to implement a Big Integer multiplication algorithm using strings to handle large numbers.Algorithm:
Find the prime factorization of each element in the array. Since the numbers are bounded by 100, we only need to consider prime factors up to 100.
For each prime number, maintain the maximum power (max_powers) encountered across all elements in the array.
Finally, initialize a string-based answer variable as "1" and multiply it sequentially with all the prime factors raised to their respective maximum powers using a custom helper function (multiplyShort).Below is the clean and optimized C++ implementation for this approach:
#include<bits/stdc++.h>
using namespace std;
string multiplyShort(string num,int x){
string res="";
int carry=0;
for(int i=num.length()-1;i>=0;i--){
long long prod=(num[i]-'0')*1LL*x+carry;
res+=to_string(prod%10);
carry=prod/10;
}
while(carry){
res+=to_string(carry%10);
carry/=10;
}
reverse(res.begin(),res.end());
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
vector<int> a(n);
vector<int> max_powers(101,0);
for(int i=0;i<n;i++){
cin>>a[i];
int temp=a[i];
for(int p=2;p*p<=temp;p++){
if(temp%p==0){
int count=0;
while(temp%p==0){
count++;
temp/=p;
}
max_powers[p]=max(max_powers[p],count);
}
}
if(temp>1){
max_powers[temp]=max(max_powers[temp],1);
}
}
string ans="1";
for(int i=2;i<=100;i++){
for(int j=0;j<max_powers[i];j++){
ans=multiplyShort(ans,i);
}
}
cout<<ans<<"\n";
return 0;
}