Return to Answer

I assume the positive integers case and rely on existence of unique prime factorizations and linear order for them.

Let $P$ be the product of all elements of $S$.

Assuming we can find prime factorization of each element of $S$ (and thus $P$), here are some quick tests for the "None" answer:

1. Test whether we can represent $P$ as the product of $m$-th and $n$-th powers. That is, the answer is "None" if for some prime $p\mid P$, we cannot represent $\nu_p(P)$ as a linear combination of $m$ and $n$ with nonnegative integer coefficients.

2. Let $k_p$ be the number of elements of $S$ divisible by $p$. For each prime $p\mid P$, the number $k_p$ must be on the form $xm+yn-xy = mn - (n-x)(m-y)$ with $0\leq x\leq n$ and $0\leq y\leq m$ (where $x$ and $y$ would be the number of elements divisible by $p$ in $B$ and $A$, respectively). That is, $mn-k_p$ must be the product of two numbers below $n$ and $m$, respectively. If not, the answer is "None".

Now, let me describe a simple backtracking algorithm that tries to fill up an empty $m\times n$ table $M$ with the elements of $S$ to turn it into a multiplication table. We assume that the elements of $S$ are sorted in non-decreasing order.

1. We place the first (smallest) element of $S$ to $M_{1,1}$.

2. For each subsequent element of $S$, we will try to place it to empty cells that are adjacent to the occupied ones (e.g., we can place the second element of $S$ either to $M_{1,2}$ and $M_{2,1}$), subject to the following constraints.

3. Placing an element $s$ to $M_{i,j}$ is allowed only if

(i) $s$ divides $$\gcd(M_{i,1},M_{i,2},\dots,M_{i,{j-1}})\cdot \gcd(M_{1,j},M_{2,j},\dots,M_{i-1,j});$$ and

(ii) if $\gcd(M_{i,1},M_{i,2},\dots,M_{i,{j-1}},s)<\gcd(M_{i,1},M_{i,2},\dots,M_{i,{j-1}})$, then we re-test as in (i) that each $M_{i,k}$ remains allowed at its position with $s$ placed at $M_{i,j}$; and

(iii) similarly we check the inequality $\gcd(M_{1,j},M_{2,j},\dots,M_{i-1,j},s)<\gcd(M_{1,j},M_{2,j},\dots,M_{i-1,j})$.

4. If conditions (i)-(iii) hold, we place $s$ to $M_{i,j}$ and iterate to step 2. If not, we go to the next potential placement for $s$. If all placements are exhausted, we return to the previous element and try to find it a new placement, etc. If this way we ever return to the first element of $S$, the answer is "None".

When the whole table is filled, we try to recover the elements of $A$ and $B$ from linear algebra on the prime exponents for each prime $p\mid P$ (perhaps, something can be done here even if we cannot factor $P$). Notice that $\gcd$'s of rows and columns give multiples of the corresponding elements of $A$ and $B$ (if they exist). If the product of $\gcd$ of $i$-th row and $\gcd$ of $j$-th column give $M_{i,j}$, then these $\gcd$'s are the elements of $A$ and $B$.

I assume the positive integers case and rely on existence of unique prime factorizations and linear order for them.

Let $P$ be the product of all elements of $S$.

Assuming we can find prime factorization of each element of $S$ (and thus $P$), here are some quick tests for the "None" answer:

1. Test whether we can represent $P$ as the product of $m$-th and $n$-th powers. That is, the answer is "None" if for some prime $p\mid P$, we cannot represent $\nu_p(P)$ as a linear combination of $m$ and $n$ with nonnegative integer coefficients.

2. Let $k_p$ be the number of elements of $S$ divisible by $p$. For each prime $p\mid P$, the number $mn-k_p$ must be equal to $x\cdot y$, where $x$ and $y$ would be the number of elements not divisible by $p$ in $A$ and $B$, respectively. That is, $mn-k_p$ must be the product of two numbers below $n$ and $m$, respectively. If not, the answer is "None".

Now, let me describe a simple backtracking algorithm that tries to fill up an empty $m\times n$ table $M$ with the elements of $S$ to turn it into a multiplication table. We assume that the elements of $S$ are sorted in non-decreasing order.

1. We place the first (smallest) element of $S$ to $M_{1,1}$.

2. For each subsequent element $s$ of $S$, we will try to place it to empty cells that are adjacent to the occupied ones (e.g., we can place the second element of $S$ either to $M_{1,2}$ and $M_{2,1}$), subject to the following constraints.

3. Placing an element $s$ to $M_{i,j}$ is allowed only if the following conditions hold:

(i) $s$ must divide $$\gcd(M_{i,1},M_{i,2},\dots,M_{i,{j-1}})\cdot \gcd(M_{1,j},M_{2,j},\dots,M_{i-1,j});$$ and

(ii) if $\gcd(M_{i,1},M_{i,2},\dots,M_{i,{j-1}},s)<\gcd(M_{i,1},M_{i,2},\dots,M_{i,{j-1}})$, then we re-test as in (i) that each $M_{i,k}$ remains allowed at its position with $s$ placed at $M_{i,j}$; and

(iii) similarly we check the inequality $\gcd(M_{1,j},M_{2,j},\dots,M_{i-1,j},s)<\gcd(M_{1,j},M_{2,j},\dots,M_{i-1,j})$ and that all these elements remain allowed at their positions.

4. If conditions (i)-(iii) hold, we place $s$ to $M_{i,j}$ and iterate to step 2. If not, we go to the next potential placement for $s$. If all placements are exhausted, we return to the previous element and try to find it a new placement, etc. If this way we ever return to the first element of $S$, the answer is "None".

When the whole table is filled, we try to recover the elements of $A$ and $B$ from linear algebra on the prime exponents for each prime $p\mid P$ (perhaps, something can be done here even if we cannot factor $P$). Notice that $\gcd$'s of rows and columns give multiples of the corresponding elements of $A$ and $B$ (if they exist). If the product of $\gcd$ of $i$-th row and $\gcd$ of $j$-th column give $M_{i,j}$, then these $\gcd$'s are the elements of $A$ and $B$.

Assuming we can find prime factorization of each element of $S$ (and thus $P$), here are some tests for "None" answer:

4. If conditions (i)-(iii) hold, we place $s$ to $M_{i,j}$ and iterate to step 2. If not, we go to the next potential placement for $s$. If all placements are exhausted, we return to the previous element and try to find it a new placement, etc. If this return to the first element this way, the answer is "None".

5. When the whole table is filled, we try to recover the elements of $A$ and $B$ from linear algebra on the prime exponents for each prime $p\mid P$ (perhaps, something can be done here even if we cannot factor $P$). Notice that $\gcd$'s of rows and columns give multiples of the corresponding elements of $A$ and $B$ (if they exist). If the product of $\gcd$ of $i$-th row and $\gcd$ of $j$-th column give $M_{i,j}$, then these $\gcd$'s are the elements of $A$ and $B$.

Assuming we can find prime factorization of each element of $S$ (and thus $P$), here are some quick tests for the "None" answer:

4. If conditions (i)-(iii) hold, we place $s$ to $M_{i,j}$ and iterate to step 2. If not, we go to the next potential placement for $s$. If all placements are exhausted, we return to the previous element and try to find it a new placement, etc. If this way we ever return to the first element of $S$, the answer is "None".

When the whole table is filled, we try to recover the elements of $A$ and $B$ from linear algebra on the prime exponents for each prime $p\mid P$ (perhaps, something can be done here even if we cannot factor $P$). Notice that $\gcd$'s of rows and columns give multiples of the corresponding elements of $A$ and $B$ (if they exist). If the product of $\gcd$ of $i$-th row and $\gcd$ of $j$-th column give $M_{i,j}$, then these $\gcd$'s are the elements of $A$ and $B$.

1. We place the first (smallest) element of $S$ to $M_{1,1}$.

2. For each subsequent element of $S$, we will try to place it to empty cells that are adjacent to the occupied ones (e.g., we can place the second element of $S$ either to $M_{1,2}$ and $M_{2,1}$), subject to the following constraints.

3. Placing an element $s$ to $M_{i,j}$ is allowed only if (i) $s$ divides $$\gcd(M_{i,1},M_{i,2},\dots,M_{i,{j-1}})\cdot \gcd(M_{1,j},M_{2,j},\dots,M_{i-1,j});$$ and (ii) if $\gcd(M_{i,1},M_{i,2},\dots,M_{i,{j-1}},s)<\gcd(M_{i,1},M_{i,2},\dots,M_{i,{j-1}})$, then we re-test as in (i) that each $M_{i,k}$ remains allowed at its position with $s$ placed at $M_{i,j}$; (iii) similarly we check the inequality $\gcd(M_{1,j},M_{2,j},\dots,M_{i-1,j},s)<\gcd(M_{1,j},M_{2,j},\dots,M_{i-1,j})$.

4. If conditions (i)-(iii) hold, we place $s$ to $M_{i,j}$ and iterate to step 2. If not, we go to the next potential placement for $s$. If all placements are exhausted, we return to the previous element and try to find it a new placement, etc. If this return to the first element this way, the answer is "None".

5. When the whole table is filled, we recover the elements of $A$ and $B$ from linear algebra on the prime exponents for each prime $p\mid P$ (perhaps, something can be done here even if we cannot factor $P$).

1. We place the first (smallest) element of $S$ to $M_{1,1}$.

2. For each subsequent element of $S$, we will try to place it to empty cells that are adjacent to the occupied ones (e.g., we can place the second element of $S$ either to $M_{1,2}$ and $M_{2,1}$), subject to the following constraints.

3. Placing an element $s$ to $M_{i,j}$ is allowed only if

(i) $s$ divides $$\gcd(M_{i,1},M_{i,2},\dots,M_{i,{j-1}})\cdot \gcd(M_{1,j},M_{2,j},\dots,M_{i-1,j});$$ and

(ii) if $\gcd(M_{i,1},M_{i,2},\dots,M_{i,{j-1}},s)<\gcd(M_{i,1},M_{i,2},\dots,M_{i,{j-1}})$, then we re-test as in (i) that each $M_{i,k}$ remains allowed at its position with $s$ placed at $M_{i,j}$; and

(iii) similarly we check the inequality $\gcd(M_{1,j},M_{2,j},\dots,M_{i-1,j},s)<\gcd(M_{1,j},M_{2,j},\dots,M_{i-1,j})$.

4. If conditions (i)-(iii) hold, we place $s$ to $M_{i,j}$ and iterate to step 2. If not, we go to the next potential placement for $s$. If all placements are exhausted, we return to the previous element and try to find it a new placement, etc. If this return to the first element this way, the answer is "None".

5. When the whole table is filled, we try to recover the elements of $A$ and $B$ from linear algebra on the prime exponents for each prime $p\mid P$ (perhaps, something can be done here even if we cannot factor $P$). Notice that $\gcd$'s of rows and columns give multiples of the corresponding elements of $A$ and $B$ (if they exist). If the product of $\gcd$ of $i$-th row and $\gcd$ of $j$-th column give $M_{i,j}$, then these $\gcd$'s are the elements of $A$ and $B$.