Smallest Square Divisible by Every Value
National Olympiad — Regional round (2019 season)
Submission name: square.cpp
Problem summary
Find the smallest positive integer c such that every input value divides c². Output c, not c².
Input
n and n positive values.
Output
The minimum c.
Constraints
1 ≤ n < 10000; 1 ≤ values < 43.
Worked example
Input and output for the worked example discussed below.
Input
4 5 2 6 4
Output
30
Solution analysis
- Factor each value and retain the maximum exponent e for every prime. These are the required exponents in the least common multiple.
- A square doubles its root’s exponents, so c must contain each prime to power ceil(e/2). Multiply exactly these minimum prime powers.
- The sample requires 2²,3¹,5¹ in the common multiple. Root 2×3×5=30 has square 900 divisible by every input.
Why it works
Prime divisibility constraints are independent and impose exactly the rounded-up half-exponent bounds on c.
Complexity: O(n sqrt A + A log A) time and O(A) space for A=42. The result fits unsigned long long.
Watch out. Round odd exponents upward and output the root. Multiplying all inputs is not minimal.
Commented C++17 solution
An independently written complete program with standard headers.
// Prime divisibility constraints are independent and impose exactly the rounded-up half-exponent bounds on c.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
int count;
cin>>count;
vector<int>exponent(43);
while(count--){
int value;
cin>>value;
for(int prime=2;prime*prime<=value;prime++){
int power=0;
while(value%prime==0){
value/=prime;
power++;
}
exponent[prime]=max(exponent[prime],power);
}
if(value>1){
exponent[value]=max(exponent[value],1);
}
}
unsigned long long answer=1;
for(int prime=2;prime<=42;prime++){
for(int power=0;power<(exponent[prime]+1)/2;power++){
answer*=prime;
}
}
cout<<answer<<'\n';
}