3
$\begingroup$

Source: https://oj.vnoi.info/problem/cryptkey (problem statements are in Vietnamese, so here it is translated).

There is a set $S$ of positive integers. If $A$ and $B$ are in $S$, then $\gcd(A, B)$ and $\text{lcm}(A, B)$ are also in $S$.

You are given $n$ positive integers $a_1$, $a_2$, ..., $a_n$, which are elements of $S$ and a positive integer $k$. Find whether $k$ must be an element of $S$.

For example, for 2 integers $45$ and $75$ and $k=15$, the answer is "YES" since $\gcd(45,75)=15$.
For example, for 2 integers $45$ and $75$ and $k=9$, the answer is "NO" since $S$ can be $\{1, 15, 45, 75, 225\}$, which does not contain $9$.

I stumbled into it and lost an entire afternoon to it. Does anyone have an idea how to start? I could theoretically run a brute-force that lasts forever, but that seems to just defeat the purpose of the question.

$\endgroup$
4
  • $\begingroup$ What do you recall about GCD, LCM and prime factors? $\endgroup$
    – greybeard
    Aug 4, 2022 at 14:37
  • $\begingroup$ GCD of N numbers can be constructed by factoring each into primes, then choose the common ones, power them with the least power (idk how to explain it), and multiply them with each other. LCM is the same, except we power each prime factor with the max power instead, and multiply them together. $\endgroup$ Aug 4, 2022 at 14:57
  • $\begingroup$ My implementation of the algorithm in my answer have been accepted by the online judge. $\endgroup$
    – John L.
    Aug 21, 2022 at 8:27
  • $\begingroup$ @MinhĐứcHoàng Have you considered upvoting and accepting my answer? Please tell me where my answer can be improved. (This comment will be deleted upon feedback.) $\endgroup$
    – John L.
    May 12 at 7:51

2 Answers 2

1
$\begingroup$

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

  1. If $k=1$, return "YES" if all $a_i$'s are relatively prime and "NO" otherwise.
  2. 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$.
  3. For $j$ from $1$ to $\ell$, do the following.
    1. Find all multiples of ${p_j}^{e_j}$ among $a_i$'s. If there is none, return "NO".
    2. If $k$ is not a multiple of the greatest common divisor of those multiples, return "NO".
  4. 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.

  1. 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$.
  2. 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}$.
  3. 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.

  1. 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.

  2. 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$

$\endgroup$
3
  • $\begingroup$ If k=1, return "YES" if *for any 1≤i<j≤n $a_i$ and $a_n$ are relatively prime and "NO" otherwise. I failed to argue 4. is correct. $\endgroup$
    – greybeard
    Aug 5, 2022 at 19:58
  • $\begingroup$ @greybeard "$a_1, \cdots, a_n$ are relatively prime" means $\gcd(a_1, \cdots, a_n)=1$. For example, if $(a_1, a_2, a_3)=(6, 10, 15)$, then $S$ contain $k=1$. $\endgroup$
    – John L.
    Aug 5, 2022 at 22:40
  • $\begingroup$ @greybeard I just made a detailed proof. $\endgroup$
    – John L.
    Aug 7, 2022 at 18:15
0
$\begingroup$

Take John’s answer. However, we don’t actually need a prime factorisation. Let’s say we have a large x which might be prime or composite (and finding out takes a long time). Instead of trying to factor x, we calculate the gcd with the other numbers. A gcd ≠ 1 means we found a factor. If all gcds are = 1 then it doesn’t matter whether x is composite or not.

With this incomplete information we can determine if k has to be an element of S.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.