If I understand the question correctly, a solution to the problem will have
the form of a (rooted) tree. Each vertex of the tree will be labeled with a
set of positive integers, which is either what remains of $A$, at the
root, or a spin-off of $A$, a spin-off of a spin-off of $A$, etc. at vertices
which are not the root. The sets of positive integers must fulfill the
following constraints:
(1) They are nonempty and disjoint;
(2) All integers in all sets divide the original lcm, $M$;
(3) The union of the sets contains the original set $A$;
(4) For each set, its gcd is divisible by its anchor, which is a member
of the set at its parent vertex (if the set is not at the root) or
a fixed, given, number $r$ not appearing in any set (if the set is at the root.)
Given such a tree, its cost is $M \sum_v (\#S_v)/a_v$, where $v$ ranges over
the vertices of the tree, $S_v$ is the set at vertex $v$, and $a_v$ is the
anchor of the set at vertex $v$.
First, observe that if a vertex is labeled with a set of size larger than 1,
$\{c_1,\ldots,c_t\}$, say, we can split it into $t$ vertices, labeled
with $\{c_1\}$, $\{c_2\}$, $\dots$, $\{c_t\}$, and reapportion its child vertices
among these vertices so that each child set is beneath its anchor. This does
not change the cost of the tree, so after doing this repeatedly,
we may assume that all sets have size 1, i.e., each
vertex is labeled with a single number. Second, observe that we may add
a vertex above the root labeled with the original anchor. These two steps
reduce the problem to the problem of finding a rooted tree whose vertices
are labeled with distinct positive integers which satisfies
(a) All labels divide $M$;
(b) The root is labeled with $r$, the original anchor;
(c) The set of labels contains the original set $A$; and
(d) the label at the top of each edge divides the label at the bottom,
and which has minimum cost, where the cost is now $M$ times
the sum over all edges of the reciprocal of the label at the top of the edge.
Also, we may now allow $r$ to be a member of $A$, and we observe that there is
no need to require the vertex labels to be distinct, since if we had two
vertices with the same label, we could construct a cheaper tree by deleting one of them and reapportioning all its children to the other.
Let $T$ be an minimum-cost tree for $r$, $M$ and $A$.
Observe that:
(i) Each of the leaves of $T$ must be
labeled with a member of $A$, since otherwise we could construct a
cheaper tree by removing a leaf.
(ii) If a vertex other than the root has exactly 1 child, it must be labeled
with a member of $A$, since otherwise it would be cheaper to remove the vertex
and reapportion its child to its parent.
(iii) If a vertex other than the root has 2 or more children and is not
labeled with a member of $A$, we can assume that its label equals the gcd of the labels of its children, since otherwise we could make a
cheaper tree by relabeling it with the gcd of the labels of its children.
(iv) Fix some parent vertex $v$ of leaves, and let it have label $l$ and leaf children
$w_1$, $\ldots$, $w_t$ with
labels $s_1$, $\ldots$, $s_t$. Then if we delete $w_1$, $\ldots$, $w_t$ from $T$, the remaining tree, $T'$, must be minimum-cost
for $r$, $M$, and the set $A\cup\{l\}\setminus\{s_1,\ldots,s_t\}$, since if
there was a cheaper tree, $T''$, say, for this set, we could make a tree cheaper
than $T$ for $A$ by attaching the children $w_1$, $\ldots$, $w_t$
to the vertex labeled $l$ in $T''$.
Rules (i)-(iv) give us a recursive algorithm for finding an optimal tree $T$.
If $A$ is empty or $A=\{r\}$, we are done since the optimal tree consists of only the
root vertex and has cost 0. Otherwise, $T$ must have at least one
leaf, and since, by (i), all leaves are labeled with a member of $A$,
there must be some subset $\emptyset\ne S\subseteq A$ and some vertex $v$
such that $v$ has only leaf children and $S$ contains
the set of labels of the set of leaves, $W$, which are children of $v$. Then, by (ii) and (iii), the label of $v$, $l$, must be either
$r$, some member of $A$, or $\gcd(S)$. Now,
let $T'$ be $T$ with the vertices in $W$ removed; by (iv), we can
compute $T'$ by calling the algorithm again to find an optimal tree for
$A\cup\{l\}\setminus S$, and then $T$ can be reconstructed by reattaching
the children $W$ to $v$. Performing this step for all possible choices of $S$ and $l$ will give a set of possibilities for $T$ from
which we can take the best possible answer.