除数最多为 10^6

Question

我一直在努力解决这个问题。

http://www.spoj.com/problems/DIV/

为了计算整数因子，我尝试了两种方法

首先：正常的 sqrt(i) 迭代。

int divCount = 2;
            for (int j = 2; j * j <= i ; ++j) {
                if( i % j == 0) {
                        if( i / j == j )
                            divCount += 1;
                        else
                            divCount += 2;
                    }
            }

第二：使用质因数分解（质数-筛）

for(int j = 0; copy != 1; ++j){
                int count = 0;
                while(copy % primes.get(j) == 0){
                    copy /= primes.get(j);
                    ++count;
                }
                divCount *= ( count + 1);}

虽然输出正确，但我得到了 TLE。可以做更多的优化吗？请帮忙。谢谢

Answer 1

您正在从错误的一端解决问题。对于任何数字

  X = p1^a1 * p2^a2 * ... * pn^an // p1..pn are prime

  d(X) = (a1 + 1)*(a2 + 1)* ... *(an + 1)

例如

  50 = 4 * 25 = 2^2 * 5^2
  d(50) = (1 + 2) * (1 + 2) = 9

  99 = 3^2 * 11^1
  d(99) = (2 + 1) * (1 + 1) = 6

到目前为止一切顺利，您需要生成所有数字，使得

   X = p1^a1 * p2^a2 <= 1e6

这样

  (a1 + 1) is prime
  (a2 + 1) is prime

有一个 table 个素数 从 1 到 1e6 这是一个毫秒任务

Answer 2

不做任何因式分解也可以解决这个问题。你只需要一个筛子。

不是由位（代表素数或合数）组成的传统埃拉托色尼筛法，而是安排您的筛子，使数组的每个元素都是指向初始为空的因子列表的指针。然后访问数组的每个元素，就像您使用 Eratosthenes 筛法一样。如果元素是非空列表，则它是复合的，因此跳过它。否则，对于每个元素及其小于限制的每个幂，将元素添加到每个幂的倍数。在此过程结束时，您将获得该数的质因数列表。这不是很清楚，所以让我举一个最多 20 的数字的例子。这是数组，最初是空的：

 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

现在我们用 2 筛分，每个倍数加 2：

 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
 2     2     2     2     2     2     2     2     2     2

因为我们也是按幂筛选，所以我们对每个 4 的倍数加 2：

 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
 2     2     2     2     2     2     2     2     2     2
       2           2           2           2           2

同样，通过 8 和 16 的每个倍数：

 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
 2     2     2     2     2     2     2     2     2     2
       2           2           2           2           2
                   2                       2
                                           2

现在我们已经完成了 2，所以我们转到下一个数字 3。3 的条目为空，因此我们筛选 3 及其 9 次方：

 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
 2     2     2     2     2     2     2     2     2     2
       2           2           2           2           2
                   2                       2
                                           2
    3        3        3        3        3        3
                      3                          3

然后我们按 5、7、11、13、17 和 19 进行筛选：

 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
 2     2     2     2     2     2     2     2     2     2
       2           2           2           2           2
                   2                       2
                                           2
    3        3        3        3        3        3
                      3                          3
          5              5              5              5
                7                    7
                            11
                                 13
                                             17
                                                   19

现在我们有了一个列表，其中包含所有小于极限的数字的所有质因数，是通过筛选而不是因式分解计算得出的。然后很容易通过扫描列表来计算除数；计算列表中每个因素的出现次数，将每个总数加 1，然后将结果相乘。例如，12 有 2 个因数 2 和 1 个因数 3，所以取 (2+1) * (1+1) = 3 * 2 = 6，实际上 12 有 6 个因数：1, 2, 3, 4, 6 和 12.

最后一步是检查除数是否恰好有两个因数。这很简单：只需查看素数除数列表并数一数即可。

因此，你没有做任何因式分解就解决了这个问题。这应该非常快，只比传统的埃拉托色尼筛法慢一点，但比分解每个数字来计算除数的数量要快得多。

唯一的潜在问题是 space 素因数列表的消耗。但是您不必为此担心太多；最大的列表将只有 19 个因子（因为最小的因子是 2，并且 2^20 大于您的限制），并且列表中的 78498 个将只有一个因子（小于一百万的素数）。

Answer 3

虽然上面提到的问题不需要计算除数的个数，但是在限定的时间(0.07s).

内计算d(N)（N的除数）还是可以解决的]

这个想法非常简单。跟踪每个数字的最小质因数 f(N)。这可以通过标准初筛完成。现在，对于每个数字 i，继续将其除以 f(i)，然后递增计数直到 i = 1。您现在已经为每个数字设置了一组素数 i。

int d[MAX], f[MAX];

void sieve() {
  for (int i = 2; i < MAX; i++) {
    if (!f[i]) {
      f[i] = i;

      for (int j = i * 2; j < MAX; j += i) {
        if (!f[j]) f[j] = i;
      }
    }

    d[i] = 1;
  }


  for (int i = 1; i < MAX; i++) {
    int k = i;

    while (k != 1) {
      int s = 0, fk = f[k];

      while (k % fk == 0) {
        k /= fk; s++;
      }

      d[i] *= (s + 1);
    }
  }
}

一旦d(N)被想通了，剩下的问题就变得简单多了。保持每个数字的最小质因数也有助于解决许多其他问题。

除数最多为 10^6

Number of divisiors upto 10^6

math

number-theory

factorization