求解等于编码和的变量：OpenVote多候选人计票问题

我来给你梳理清楚这个多候选人选举计票分解的问题，结合原方案的背景和解决思路：

处理多候选人的首选方法是采用Baudron等人提出的方案：假设共有n个选民，选择最小的整数m使得2^m > n。候选人1的选票编码为2^0，候选人2为2^m，候选人3为2^(2*m)，依此类推。换言之，重新定义相关编码规则后，计票方式与此前类似：Π (g^xi*yi)*g^vi = g^Σvi。将选票求和后，编码的超递增特性确保总结果可唯一分解为各候选人的得票总数。因此，Σvi = 2^0 * c1 + 2^m * c2 + ... + 2^(k-1)m * ck，其中c₁至cₖ分别为k位候选人的得票数。与此前相同，该分解需遍历可能的组合，但预计算高概率组合可提升效率。

核心问题 #

给定Σv的值，如何找到满足如下方程的c₁至cₖ？

其中k为候选人数量，m是满足2^m > 最大得票数的最小整数。

搜索空间优化条件 #

我们可以利用以下条件来大幅缩小需要遍历的组合范围，提升分解效率：

• 单个候选人的最大得票数max(c₁,c₂,...,cₖ)等于记录的总票数
• 存在唯一的一组c₁至cₖ满足当前Σv的值
• 所有候选人得票数之和Σc ≤ 记录的总票数

内容的提问来源于stack exchange，提问作者iH8WorkingWith.NetGraphics