## Intuition The problem requires finding the smallest positive integer `n` such that the fraction \( \frac{n!}{a_1 \times a_2 \times \ldots \times a_k} \) is a positive integer. This means that `n!` should be divisible by the product of all `a_i`. The key insight is that for `n!` to be divisible by a number, `n!` must contain all prime factors of that number with at least the same multiplicity. ## Approach 1. **Prime Factorization**: First, we need to determine the prime factorization of the product of all `a_i`. This involves finding the maximum power of each prime that divides any of the `a_i`. 2. **Binary Search on `n`**: We will use binary search to find the smallest `n` such that `n!` contains all the required prime factors with the necessary multiplicity. For each `n`, we check if `n!` can be divided by the product of all `a_i` by comparing the prime factor multiplicities. 3. **Checking Divisibility**: For a given `n`, calculate the prime factorization of `n!` and check if it satisfies the conditions derived from the product of `a_i`. 4. **Optimization Considerations**: The factorial grows very fast, so we can use binary search efficiently. The upper bound for `n` can be reasonably set based on the constraints, considering that `n!` grows rapidly. ## Complexity - **Time Complexity**: The time complexity is approximately \( O(k \cdot \log(\text{max } a_i) + \log(\text{upper bound for } n) \cdot \log(\text{upper bound for } n)) \), where the first term is for factorizing the product and the second is for checking each `n` in the binary search. - **Space Complexity**: \( O(\text{number of distinct primes}) \), which is small compared to `k`. ## Solution (C++) ```cpp #include using namespace std; // Function to compute the prime factorization of a number map primeFactorize(int x) { map factors; for (int i = 2; i * i <= x; ++i) { while (x % i == 0) { factors[i]++; x /= i; } } if (x > 1) { factors[x]++; } return factors; } // Function to check if n! contains all required prime factors bool canDivide(int n, const map& requiredFactors) { map factorialFactors; for (int i = 2; i <= n; ++i) { int num = i; for (auto& [prime, _] : requiredFactors) { while (num % prime == 0) { factorialFactors[prime]++; num /= prime; } } } for (const auto& [prime, count] : requiredFactors) { if (factorialFactors[prime] < count) { return false; } } return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int k; cin >> k; vector a(k); for (int i = 0; i < k; ++i) { cin >> a[i]; } // Calculate the required prime factors map requiredFactors; for (int i = 0; i < k; ++i) { map factors = primeFactorize(a[i]); for (const auto& [prime, count] : factors) { requiredFactors[prime] = max(requiredFactors[prime], count); } } // Binary search for the smallest n int left = 1, right = 1e6; // Reasonable upper bound for n while (left < right) { int mid = left + (right - left) / 2; if (canDivide(mid, requiredFactors)) { right = mid; } else { left = mid + 1; } } cout << left << "\n"; return 0; } ``` This solution efficiently finds the smallest `n` using binary search and checks the divisibility condition by comparing prime factor multiplicities.

Empire Strikes Back

Problem Details