algorithm - 求解等于编码总和的变量

Question

问题来自here

A preferred way to deal with multiple candidates is to use the method because of Baudron et al. [16]: suppose that we have n voters, choose m so that m is the smallest integer such that 2^m > n. Now a vote for candidate 1 is encoded as 2^0 , for candidate 2 as 2^m, for candidate 3 is 2^(2*m) and so on. In other words, redefine (1) as

Tabulation is much as before: Π (g^xi*yi)*g^vi = g^Σvi. The votes are summed and the super-increasing nature of the encoding ensures that the total can unambiguously be resolved into the totals for the candidates. Hence, Σvi = 2^0 * c1 + 2^m * c2 + ... + 2^(k-1)m * ck where c1 to ck are the counts of votes for the k candidates correspondingly. As before, this resolution requires searching over possible combinations, but of course pre-computation over (the more likely) combinations could speed this up.

基本上给定 v 的总和，如何找到 c 使得这个等式成立:

其中 k 是候选人的数量，m 是满足 2 ^ m > max # of votes 的最小整数。

一些可能对限制搜索空间有用的东西:

• max(c) = 记录的票数
• 存在一组唯一的 c 等于某个和 v
• c 的总和 <= 记录的票数

Answer 1

条件2^m > n对制定公式至关重要

Σvi = 2^0 * c1 + 2^m * c2 + ... + 2^(k-1)m * ck

从总和到 ci 是可逆的.你没有指定你的环境，所以我将使用一些 C 风格的伪代码

tmp = sum;
p = power(2,m);
for(i = 0; i< k; i++) {
    c[i] = tmp % p; // i.e. calculate reminder, often also called mod
    tmp = tmp / p;  // whole division on (big) integers
}

这应该有效，因为条件 2^m > n确保自 ci <= n如此传递ci < 2^m因此不会有“溢出”。本质上，这里的想法是将投票计数表示为一个具有巨大 2^m 的系统中的数字。每个数字只是相应候选人的票数。