已知：随机数生成元件等概率返回 $[0,p)$ 中的整数，要构造一个以概率比 $a_0:a_1:...:a_n(\gcd(a_i)=1)$ 返回 $[0,n)$ 中的整数的随机数生成器，求元件的最小期望使用次数。

设第 $i$ 次返回的结果分配了 $K_{i,j}$ 个给返回值 $j$。则：

$$ \begin{array} \forall j ,\sum_i p^{-i}K_{i,j}=\frac{a_j}{\sum a} & (1)\\ \text{minimum.} \sum_{i,j}ip^{-i}K_{i,j} & (2) \end{array} $$

引理1 $\forall i,j ,K_{i,j}\in [0,p) $

证：使用调整法：

若 $\forall i,j ,K_{i,j}\neq p $，由 $(1)$ 有 $i>0$ ，则可令 $K_{i-1,j}$ 增加 $1$，$K_{i,j}$ 减少 $p$，显然 $(1)$ 式仍成立。

$(2)$ 式的改变量为 $(i-1)p^{-i+1}-pip^{-i}=-p^{-i+1} < 0$ ，得到了一个更优解。

证毕。

现在来构造 $K$。考虑返回值为 $j$ 的情况，取出 $K$ 的第 $j$ 列向量，设为 $\vec{k}$。

则 $\vec{k}$ 是 $p$ 进制的 $\frac{a_j}{\sum a}$ 的位向量。当 $\sum a$ 是 $p$ 的幂时有两解，取最后为 $0$ 循环的一解；否则 $\vec{k}$ 是唯一的。证明从略。

至此找到了一个下界 $K$。在决策树上第 $i$ 层给 $j$ 分配 $K_{i,j}$ 个点，用归纳法可以证明方案是存在的。

另外可得推论：

推论1 “$a$ 是有理数”与“存在一个有 $n$ 个终态，字符集为 $[0,p)$ ，按随机数生成元件的结果转移，返回终止的状态的DFA满足条件。”是等价的。

证明从略。解释说明：由于 DFA 是有限状态的，因而对应的概率是循环小数（有理数）。反之则可用上述方法构造。