The idea
Without listing all elements in $S$, we can, following a usual approach, try checking whether $k$ is in $S$ "from the perspective of each distinct prime factor" of $k$. The subtlety and the difficulty is how and what we can do at each distinct prime factor.
A simple and fast algorithm
- If $k=1$, return "YES" if all $a_i$'s are relatively prime and "NO" otherwise.
- Now $k$ has at least one prime factor. Factorize $k$ to obtain $k=\prod_{j=1}^\ell{p_j}^{e_j}$, where $\ell\ge1$, $p_j$ is a prime, $e_j\ge1$ for all $j=1, \cdots, \ell$.
- For $j$ from $1$ to $\ell$, do the following.
- Find all multiples of ${p_j}^{e_j}$ among $a_i$'s. If there is none, return "NO".
- If $k$ is not a multiple of the greatest common divisor of those multiples, return "NO".
- Return "YES".
Time-complexity and space complexity
The algorithm runs in $O(\sqrt{M}+\max(n,\log M)\max(1, \log M))$ time, where $M=\max(a_1,\cdots, a_n)$.
It can be implemented with $O(1)$ auxiliary space.
An implementation in Python runs well within half a second for each test case at the online judge, where $n\le 50000$ and $M\le10^{12}$. Of course, your mileage might vary.
Proof of Correctness.
Call a set of positive integers dm-closed if it is closed under gcd and lcm.
Let $U$ be the set of all factors of the least common multiples of all $a_i$'s. Verify that $U$ is a dm-closed set that contain all $a_i$'s.
Let us prove that the algorithm returns 'NO' $\implies$ $k$ is not in some dm-closed set that contains all $a_i$'s. There are three cases.
- The algorithm returns 'NO' at step 1.1. That means there is a number $h>1$ such that all $a_i$'s are multiples of $h$. Consider the set of all numbers in $U$ that are multiples of $h$.
That set is a dm-closed set that contains all $a_i$'s but does not contain $k=1$.
- The algorithm returns 'NO' at step 3.1. That means for some $j$, no $a_i$ is a multiple of ${p_j}^{e_j}$. Consider the set of all numbers in $U$ that are not multiples of ${p_j}^{e_j}$.
That set is a dm-closed set that contains all $a_i$'s, which does not contain $k$, since $k$ is a multiple of ${p_j}^{e_j}$.
- The algorithm returns 'NO' at step 3.2. That means for some $j$, $k$ is not a multiple of $g_j$, the greatest common divisor of all $a_i$'s that are multiples of ${p_j}^{e_j}$. Consider set
$$D=\{u\in U\mid \text{either }u\text{ is not a multiple of }{p_j}^{e_j}\text{ or }u\text{ is a multiple of }g_j\}.$$
$D$ is a dm-closed set that contains all $a_i$'s, which does not contain $k$, since $k$ is a multiple of ${p_j}^{e_j}$ but not a multiple of $g_j$.
Let us prove that the algorithm returns 'YES' $\implies$ $k$ is in every dm-closed set that contains all $a_i$'s. Let $S$ be an arbitrary dm-closed set that contains all $a_i$'s. There are two cases.
The algorithm returns 'YES' at step 1.1. That means the greatest common divisor of all $a_i$'s is 1. Since $S$ is closed under gcd and $S$ contains all $a_i$'s, $S$ must contain 1.
The algorithm returns 'YES' at step 4. That means the algorithm does not return at step 3.1 nor at step 3.2. So, for all $j$, $k$ is a multiple of $g_j$, the greatest common divisor of all $a_i$'s that are multiples of ${p_j}^{e_j}$. Note that $g_j$ is a multiple of ${p_j}^{e_j}$. Let $h$ be the least common multiple of all $g_j$. Note that all $g_j$ are in $S$, and hence so is $h$.
- Since for all $j$, $k$ is a multiple of $g_j$, $k$ is a multiple of $h$.
- Since for all $j$, $g_j$ is a multiple of ${p_j}^{e_j}$, so is $h$. Since ${p_j}^{e_j}$'s are pairwise relatively prime, $h$ is a multiple of $k$, the product of all ${p_j}^{e_j}$'s.
So $k$ and $h$ are multiples to each other. Hence $k=h$. Since $h$ is in $S$, so is $k$. $\quad\checkmark$