PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Authors: naisheel, jalp1428
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
2673
PREREQUISITES:
PROBLEM:
Given an array of integers, find the smallest positive integer that doesn’t appear as the LCM of any of its subsequences.
EXPLANATION:
Suppose we have two subsequences S_1 and S_2 of the array.
Let L_1 = \text{lcm}(S_1) and L_2 = \text{lcm}(S_2).
Then, observe that \text{lcm}(S_1\cup S_2) = \text{lcm}(L_1, L_2).
That is, if we take both subsequences together, the LCM of their union is simply the LCM of their LCMs.
This follows from the fact that LCM is an associative operation, i.e, \text{lcm}(x, y, z) = \text{lcm}(x, \text{lcm}(y, z)) = \text{lcm}(\text{lcm}(x, y), x)) (a proof of this fact can be found here, tl;dr look at prime factorizations).
What does this mean for the task at hand though?
Well, suppose our answer is X.
Then, X is the smallest positive number that isn’t the LCM of any subsequence of A — in particular, every positive integer smaller than X is the LCM of some subsequence.
But then, if there exist integers a and b such that a, b\lt X and \text{lcm}(a, b) = X, our earlier observation tells us that we’ll be able to obtain X as the LCM of the union of their corresponding subsequences.
So, the answer must be an integer X such that X cannot be written as the LCM of two integers strictly smaller than it.
The only such integers are powers of prime numbers!
Why?
If X = p^k for some prime p, it’s easy to see that it can’t be the LCM of two smaller numbers.
The only factors of X are themselves powers of p, and the LCM of two powers of p is just the larger power; so if the LCM equals X, one of the numbers should equal X.
On the other hand, suppose X has at least two different prime factors, say p and q.
Then, \text{lcm}(\frac{X}{p}, \frac{X}{q}) = X so it’s the LCM of two numbers strictly smaller than it.
Our task is now to find the smallest prime power that doesn’t appear as the LCM of some subsequence.
As noted in the proof above though, the only way a prime power can be the LCM of some integers, is if it itself is one of them.
In other words, we just need to find the smallest prime power that doesn’t appear in A.
This can be done in an almost brute-force fashion.
First, find the first 10^5 + 1 prime powers: since N \leq 10^5, the answer is definitely among them.
This can be done using the sieve of Eratosthenes to precompute all primes upto a reasonable limit, then compute all their powers upto a reasonable limit, and take the first 10^5 of them.
In our case, the maximum answer is just under 1.3\cdot 10^6, so any limit \geq that will work.
Then, simply iterate across this sorted list of prime powers and find the smallest one that isn’t in A.
This is easy to do with, for example, binary search.
TIME COMPLEXITY
\mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
// -------------------- Input Checker Start --------------------
// This function reads a long long, character by character, and returns it as a whole long long. It makes sure that it lies in the range [l, r], and the character after the long long is endd. l and r should be in [-1e18, 1e18].
long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, fi = -1;
bool is_neg = false;
while(true)
{
char g = getchar();
if(g == '-')
{
if(!(fi == -1))
cerr << "- in between integer\n";
assert(fi == -1);
is_neg = true; // It's a negative integer
continue;
}
if('0' <= g && g <= '9')
{
x *= 10;
x += g - '0';
if(cnt == 0)
fi = g - '0'; // fi is the first digit
cnt++;
// There shouldn't be leading zeroes. eg. "02" is not valid and assert will fail here.
if(!(fi != 0 || cnt == 1))
cerr << "Leading zeroes found\n";
assert(fi != 0 || cnt == 1);
// "-0" is invalid
if(!(fi != 0 || is_neg == false))
cerr << "-0 found\n";
assert(fi != 0 || is_neg == false);
// The maximum number of digits should be 19, and if it is 19 digits long, then the first digit should be a '1'.
if(!(!(cnt > 19 || (cnt == 19 && fi > 1))))
cerr << "Value greater than 1e18 found\n";
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if(g == endd)
{
if(is_neg)
x = -x;
if(!(l <= x && x <= r))
{
// We've reached the end, but the long long isn't in the right range.
cerr << "Constraint violated: Lower Bound = " << l << " Upper Bound = " << r << " Violating Value = " << x << '\n';
assert(false);
}
return x;
}
else if((g == ' ') && (endd == '\n'))
{
cerr << "Extra space found. It should instead have been a new line.\n";
assert(false);
}
else if((g == '\n') && (endd == ' '))
{
cerr << "A new line found where it should have been a space.\n";
assert(false);
}
else
{
cerr << "Something weird has happened.\n";
assert(false);
}
}
}
string readString(int l, int r, char endd)
{
string ret = "";
int cnt = 0;
while(true)
{
char g = getchar();
assert(g != -1);
if(g == endd)
break;
cnt++;
ret += g;
}
if(!(l <= cnt && cnt <= r))
cerr << "String length not within constraints\n";
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
void readEOF()
{
char g = getchar();
if(g != EOF)
{
if(g == ' ')
cerr << "Extra space found where the file shold have ended\n";
if(g == '\n')
cerr << "Extra newline found where the file shold have ended\n";
else
cerr << "File didn't end where expected\n";
}
assert(g == EOF);
}
vector<int> readVectorInt(int n, long long l, long long r)
{
vector<int> a(n);
for(int i = 0; i < n - 1; i++)
a[i] = readIntSp(l, r);
a[n - 1] = readIntLn(l, r);
return a;
}
bool checkStringContents(string &s, char l, char r) {
for(char x: s) {
if (x < l || x > r) {
cerr << "String is not valid\n";
return false;
}
}
return true;
}
bool isStringBinary(string &s) {
return checkStringContents(s, '0', '1');
}
bool isStringLowerCase(string &s) {
return checkStringContents(s, 'a', 'z');
}
bool isStringUpperCase(string &s) {
return checkStringContents(s, 'A', 'Z');
}
bool isArrayDistinct(vector<int> a) {
sort(a.begin(), a.end());
for(int i = 1 ; i < a.size() ; ++i) {
if (a[i] == a[i-1])
return false;
}
return 1;
}
bool isPermutation(vector<int> &a) {
int n = a.size();
vector<int> done(n);
for(int x: a) {
if (x <= 0 || x > n || done[x-1]) {
cerr << "Not a valid permutation\n";
return false;
}
done[x-1]=1;
}
return true;
}
// -------------------- Input Checker End --------------------
const int N=1e7+1;
bool isp[N];
int divsr[N];
vector<int> pr;
set<int> st;
void build_primes() // 79000 primes for N=1e6 in O(N)
{
divsr[1]=1;
for(int i=2;i<N;i++)
{
if(divsr[i]==0)
{
divsr[i]=i;
isp[i]=1;
pr.push_back(i);
}
for (int j=0;j<(int)pr.size() && pr[j]<=divsr[i] && i*pr[j]<N;j++)
divsr[i*pr[j]]=pr[j];
}
for(auto z:pr){
st.insert(z);
}
}
int sn=0;
void solve(){
int n;
n=readIntLn(1,1e5);
sn+=n;
int arr[n];
for(int i=0;i<n;i++){
if(i!=n-1){
arr[i]=readIntSp(1,1e9);
}
else{
arr[i]=readIntLn(1,1e9);
}
}
map<int,int> mp;
set<int> curprs;
for(int i=0;i<n;i++){
mp[arr[i]]++;
if(st.count(arr[i])){
curprs.insert(arr[i]);
st.erase(arr[i]);
}
}
long long int ans=1e18;
if(mp[1]==0){
cout<<1<<endl;
for(auto z:curprs){
st.insert(z);
}
return;
}
for(auto z:curprs){
if(z>ans)break;
long long int num=z;
while(mp[num]){
num*=z;
}
ans=min(ans,num);
}
ans=min(ans,(long long int)(*st.begin()));
cout<<ans<<endl;
for(auto z:curprs){
st.insert(z);
}
}
int main(){
int tc;
tc=readIntLn(1,1000);
build_primes();
while(tc--){
solve();
}
readEOF();
assert(sn<=1e5);
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
string readOne() {
assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
res += buffer[pos];
assert(!isspace(buffer[pos]));
pos++;
}
return res;
}
string readString(int min_len, int max_len, const string& pattern = "") {
assert(min_len <= max_len);
string res = readOne();
assert(min_len <= (int) res.size());
assert((int) res.size() <= max_len);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int min_val, int max_val) {
assert(min_val <= max_val);
int res = stoi(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
long long readLong(long long min_val, long long max_val) {
assert(min_val <= max_val);
long long res = stoll(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
vector<int> readInts(int size, int min_val, int max_val) {
assert(min_val <= max_val);
vector<int> res(size);
for (int i = 0; i < size; i++) {
res[i] = readInt(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
vector<long long> readLongs(int size, long long min_val, long long max_val) {
assert(min_val <= max_val);
vector<long long> res(size);
for (int i = 0; i < size; i++) {
res[i] = readLong(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
struct sieve {
vector<int> primes;
vector<bool> is_prime;
vector<int> min_factor;
sieve(int MAX = 1 << 21) {
is_prime = vector<bool>(MAX, true);
min_factor = vector<int>(MAX);
is_prime[0] = is_prime[1] = false;
min_factor[0] = min_factor[1] = 1;
for (int i = 2; i < MAX; i++) {
if (!is_prime[i]) {
continue;
}
primes.emplace_back(i);
min_factor[i] = i;
if ((long long) i * i >= MAX) {
continue;
}
for (int j = i * i; j < MAX; j += i) {
if (is_prime[j]) {
is_prime[j] = false;
min_factor[j] = i;
}
}
}
}
vector<pair<int, int>> factor(int n) {
vector<pair<int, int>> res;
while (n != 1) {
int p = min_factor[n];
res.emplace_back(p, 0);
while (p == min_factor[n]) {
n /= p;
res.back().second++;
}
}
reverse(res.begin(), res.end());
return res;
}
vector<int> divisor(int n) {
vector<int> res(1, 1);
for (const auto& p : factor(n)) {
for (int i = (int) res.size() - 1; i >= 0; i--) {
int c = res[i];
for (int j = 0; j < p.second; j++) {
c *= p.first;
res.emplace_back(c);
}
}
}
sort(res.begin(), res.end());
return res;
}
vector<int> mu_table() {
vector<int> res(min_factor.size());
for (int i = 1; i < (int) min_factor.size(); i++) {
if (i == 1) {
res[i] = 1;
} else if ((i / min_factor[i]) % min_factor[i] == 0) {
res[i] = 0;
} else {
res[i] = -res[i / min_factor[i]];
}
}
return res;
}
// zeta: add
// mobius: subtract
// zeta <-> mobius
template <typename T>
void divisor_zeta(vector<T>& a) {
int n = (int) a.size();
for (int p : primes) {
if (p >= n) {
break;
}
for (int i = 1; p * i < n; i++) {
a[p * i] += a[i];
}
}
}
template <typename T>
void divisor_mobius(vector<T>& a) {
int n = (int) a.size();
for (int p : primes) {
if (p >= n) {
break;
}
for (int i = (n - 1) / p; i >= 1; i--) {
a[p * i] -= a[i];
}
}
}
template <typename T>
void multiple_zeta(vector<T>& a) {
int n = (int) a.size();
for (int p : primes) {
if (p >= n) {
break;
}
for (int i = (n - 1) / p; i >= 1; i--) {
a[i] += a[p * i];
}
}
}
template <typename T>
void multiple_mobius(vector<T>& a) {
int n = (int) a.size();
for (int p : primes) {
if (p >= n) {
break;
}
for (int i = 1; p * i < n; i++) {
a[i] -= a[p * i];
}
}
}
};
int main() {
input_checker in;
int tt = in.readInt(1, 1e3);
in.readEoln();
sieve si;
int sn = 0;
while (tt--) {
int n = in.readInt(1, 1e5);
in.readEoln();
sn += n;
auto a = in.readLongs(n, 1, 1e9);
in.readEoln();
set<int> st(a.begin(), a.end());
int ans = (int) 2e9;
if (*st.begin() != 1) {
cout << 1 << '\n';
continue;
}
for (int p : si.primes) {
if (p > ans) {
break;
}
int q = 1;
while (q * 1LL * p < (long long) 2e9) {
q *= p;
if (st.count(q)) {
continue;
} else {
ans = min(ans, q);
break;
}
}
}
cout << ans << '\n';
}
cerr << sn << endl;
assert(sn <= 1e5);
in.readEof();
return 0;
}
Editorialist's code (Python)
mx = 2*10**6
sieve = [0]*mx
primes = []
primepows = [1]
for i in range(2, mx):
if sieve[i] == 1: continue
for j in range(2*i, mx, i): sieve[j] = 1
for i in reversed(range(2, mx)):
if sieve[i] == 0:
j = i
while j < mx:
sieve[j] = 0
j *= i
for i in range(2, mx):
if sieve[i] == 0: primepows.append(i)
for _ in range(int(input())):
n = int(input())
a = set(map(int, input().split()))
ans = mx
for p in primepows:
if p not in a:
ans = p
break
print(ans)