## Intuition The problem requires us to determine the minimum set of divisors such that, by knowing the divisibility of a number `x` by these divisors, we can uniquely identify `x` among all numbers from `1` to `n`. The key insight is to use prime numbers as divisors because they are the building blocks of all numbers. By checking divisibility with prime numbers, we can effectively narrow down the possibilities for `x`. ## Approach 1. **Prime Numbers**: Start by identifying all prime numbers up to `n`. These will be our potential divisors. 2. **Divisors Selection**: For each prime number `p`, consider all powers of `p` (i.e., `p, p^2, p^3, ...`) that are less than or equal to `n`. These powers are important because if a number is divisible by a higher power of a prime, it is also divisible by the prime itself. 3. **Output**: The sequence of these prime powers will be our questions. This sequence will be sufficient to uniquely determine any number from `1` to `n`. ## Complexity - **Time**: O(n log log n) due to the Sieve of Eratosthenes used for finding prime numbers. - **Space**: O(n) for storing the list of prime numbers and their powers. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector is_prime(n + 1, true); vector questions; // Sieve of Eratosthenes to find all primes up to n for (int i = 2; i <= n; ++i) { if (is_prime[i]) { // Add all powers of this prime that are <= n for (int power = i; power <= n; power *= i) { questions.push_back(power); } // Mark all multiples of i as non-prime for (int j = i * 2; j <= n; j += i) { is_prime[j] = false; } } } // Output the number of questions and the questions themselves cout << questions.size() << '\n'; for (int q : questions) { cout << q << ' '; } cout << '\n'; return 0; } ``` This solution efficiently finds all prime numbers up to `n` using the Sieve of Eratosthenes and then considers all powers of these primes that do not exceed `n`. This ensures that we ask the minimum number of questions to uniquely determine any number between `1` and `n`.

Vasya and Petya's Game

Problem Details