数论算法.该细分市场上的大多数除数

Question

我正在寻找一种有效的算法来解决以下问题.让d(n)表示正除数的数n,其中n为正整数.我们给了一些 1 <= a <= b <= 10^18 ,任务是找到最大值的d段[a..b]和(可能我们需要更复杂的算法,这部分)找到最大化值的数字d.

前段时间我在免费访问中找到了以下代码:http://ideone.com/qvxPj

unsigned long long n, res;
int p, primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 51, 53, 59, 61, 67, 71};

unsigned long long mul(unsigned long long a, unsigned long long b){
    unsigned long long res = 0;

    while (b){
        if (b & 1LL) res = (res + a);
        if (res >= n) return 0;
        a = (a << 1LL);
        b >>= 1LL;
    }

    return res;
}

void backtrack(int i, int lim, unsigned long long val, unsigned long long r){
    if (r > res) res = r;
    if (i == p) return;

    int d;
    unsigned long long x = val;

    for (d = 1; d <= lim; d++){
        x = mul(x, primes[i]);
        if (x == 0) return;
        backtrack(i + 1, d, x, r * (d + 1));
    }
}

int main(){    
    p = sizeof(primes) / sizeof(int);

    while (scanf("%llu", &n) != EOF){
        res = 0;
        backtrack(0, 100, 1, 1);
        printf("Maximum number of divisors of any number less than %llu = %llu\n", n, res);
    }
    return 0;
}

如果有人向我解释它是如何工作的,我将非常高兴,因为(至于我)这个程序运行得非常快.

在此先感谢您的帮助.

Answer 1

它会像这样迭代所有数字：

num = P1^D1 * P2^D2 * P3^D3 * ... * Ps^Ds
constraints:
  Pi <= 71
  1 <= Di <= 100
  sequence (Pi) is a sorted list of first s primes
  sequence (Di) is nonincreasing
  num <= n

让我们检查第一个约束。假设最小最优数的素因数q > 71。如果这个数中没有使用任何素数p <= 71 ，那么我们可以用p的同次幂代替q 。显然，除数的数量将保持不变，但数量会减少 -> 矛盾。那么就没有小于 71 的未使用素数。但是 71 以内的所有素数的乘积已经如此之大，以至于我们考虑的数字必须大于 64 位n。那是不可能的。

现在我们来解释第二个和第三个约束。假设我们的最小最优数在其分解中具有素数q，但没有素数p，其中p < q。然后我们可以以相同的顺序将q替换为p，该数字将具有相同数量的约数，但它会变得更少->矛盾。这意味着所寻求的最佳（最小）数因式分解中的所有素数必须恰好是前s个素数。使用的素数组中不能有空洞。顺便说一句，Di <= 100是显而易见的，因为即使 2^100 也已经不适合 64 位整数了。

现在我们必须解释第四个约束。假设对于某些i ， D[i] < D[i+1]。然后我们可以将P[i]^D[i] * P[i+1]^D[i+1]替换为P[i]^D[i+1] * P[i+1]^D[i ]，并且数字会变小。例如，将 5^2 * 7^3 替换为 5^3 * 7^2：约数相同，但结果较小。显然，如果我们搜索最小最优数，我们也可以安全地假设这个条件。

现在让我们考虑一下代码。 mul是一个计算a和b的乘积的小函数。它是通过一个有趣的二进制过程计算的。此过程的主要原因是：如果乘积大于n，则函数返回 0。此过程只是为了防止否则可能发生的溢出。

最后，我们必须backtrack。这是通常的递归搜索。val是当前数字，r是它的除数数，i显示我们现在要添加的素数的索引，lim将每个素数的幂限制为 100。一开始您会看到当前最佳答案的更新（存储在 中res），并且很难停止条件（使用所有素数）。

然后有一个循环检查当前素数的每个幂。它从 1 次幂开始，因为零次幂是被禁止的。它维护当前数字 inx并将其乘以Pi每次迭代以增加幂。如果x大于n，则立即停止。最后，它调用自身来搜索下一个素数。