1

我已经解决了一个问题：
给定一个自然数 n (1 <= n <= 500000)，请输出其所有适当除数的总和。

定义：自然数的适当除数是严格小于该数的除数。

例如，数字 20 有 5 个真除数：1、2、4、5、10，除数之和为：1 + 2 + 4 + 5 + 10 = 22。

输入

一个整数，表示测试用例的数量（大约等于 200000），后面有许多行，每行包含一个介于 1 和 500000 之间的整数（包括 1 到 500000）。

输出

每行一个整数：分别给定的整数的除数和。

例子

样本输入：

3
2
10
20

样本输出：

1
8
22

我的代码如下：

/* @BEGIN_OF_SOURCE_CODE */

#include <stdio.h>
#include <stdlib.h>

    int main(int argc, const char * argv[])
    {
        int sum = 0,
        cases = 0,
        i, j, buff;

        scanf("%d", &cases); //Number of tests


        int *n;
        n = (int*) malloc(cases * sizeof(int)); //Defining array for numbers to be tested///////

        for (i = 0; i < cases; i++) {
            scanf("%d", &n[i]);
        }
        for (i = 0; i < cases; i++ ) {
            buff = n[i] / 2;
            if (n[i] == 1) {
                sum = -1;
            }


            if (!(n[i] & 1)) {
                for (j = 2; j < buff; j++) {
                    if (n[i] % j == 0) {
                        sum += n[i] / j + j;
                        buff /= j;
                    }
                }
            }


            else {
                for (j = 3; j < buff; j += 2) {
                    if (n[i] % j == 0) {
                        if (n[i] / j == j) { sum += j; break; }
                        else sum += n[i] / j + j;
                    }
                    buff /= j;
                }
             }
            printf("%d\n", ++sum);
            sum = 0;
        }
        return 0;
    }
    /* @END_OF_SOURCE_CODE */

但这还不够快。有什么建议么？

4

6 回答 6

7

我已经更新了下面的代码以更快地终止。在使用 Apple GCC 4.2.1 和 -O3 编译的 MacBookPro6,1（2.66 GHz Intel Core i7）上运行从 1 到 500,000 的所有整数需要不到半秒的时间。

它使用Wikipedia 页面的“属性”部分中的σ x ( n )公式作为除数函数。使用预先计算的素数列表可以使其更快。（需要 126 来支持高达 500,000 的输入，这将时间减少到不到 1/4 秒。）还有一些可以消除的除法，但代价是代码略微混乱。

//  Return the least power of a that does not divide x.
static unsigned int LeastPower(unsigned int a, unsigned int x)
{
    unsigned int b = a;
    while (x % b == 0)
        b *= a;
    return b;
}


//  Return the sum of the proper divisors of x.
static unsigned int SumDivisors(unsigned int x)
{
    unsigned int t = x;
    unsigned int result = 1;

    //  Handle two specially.
    {
        unsigned int p = LeastPower(2, t);
        result *= p-1;
        t /= p/2;
    }

    //  Handle odd factors.
    for (unsigned int i = 3; i*i <= t; i += 2)
    {
        unsigned int p = LeastPower(i, t);
        result *= (p-1) / (i-1);
        t /= p/i;
    }

    //  At this point, t must be one or prime.
    if (1 < t)
        result *= 1+t;

    return result - x;
}
于 2013-09-16T20:44:38.897 回答
2

您不必分配空间。就一行一行的做。对于每一行，都有一个 O( n ^ 1/2 ) 算法。

#include <iostream>
using std::cout; using std::endl; using std::cin;

int main() {
   int count, number;
   cin >> count;
   for (int i = 0; i < count; ++i) {
      cin >> number;
      int sum = 1;
      for ( int j = 2; j * j <= number; ++j ) {
         if ( number % j == 0 ) {
            sum += j;
            sum += number / j;
         }
         if ( j * j == number ) sum -= j; // recalculate twice
      }
      cout << sum << endl;
   }
}

这是 200,000 个测试用例的运行时

real    0m55.420s
user    0m0.016s
sys     0m16.124s
于 2013-09-16T20:18:49.880 回答
0

假设您有一种方法可以相对快速地计算素数。这可能是一次性的前期活动，以最大输入值的平方根为界。在这种情况下，您已经知道最大输入值 (500000) 的界限，因此您可以简单地将素数表硬编码到程序中。

static unsigned P[] = {
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233,
239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,
613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701
};

static int P_COUNT = sizeof(P)/sizeof(*P);

现在，根据素数，对于每个输入值，您可以：

  • 计算素数分解
  • 计算每个素因子的幂和的乘积。

这将导致除数的总和。从总和中减去输入值以获得适当除数的总和。这两个步骤可以组合成一个循环。

该算法之所以有效，是因为多项式相乘自然会导致多项式项的所有组合相乘的总和。在每个多项式项由除输入的素数幂组成的情况下，相乘的项的组合构成除数。该算法速度很快，并且应该能够在 Core i3 或更好的处理器上在不到一秒的时间内处理区间 [1, 500000] 中的 500000 个数字。

下面的函数实现了上述方法。

unsigned compute (unsigned n) {
    unsigned sum = 1;
    unsigned x = n;
    for (int i = 0; i < P_COUNT; ++i) {
        if (P[i] > x / P[i]) break;    /* remaining primes won't divide x */
        if (x % P[i] == 0) {           /* P[i] is a divisor of n */
            unsigned sub = P[i] + 1;   /* add in power of P[i] */
            x /= P[i];                 /* reduce x by P[i] */
            while (x % P[i] == 0) {    /* while P[i] still divides x */
                x /= P[i];             /* reduce x */
                sub = sub * P[i] + 1;  /* add by another power of P[i] */
            }
            sum *= sub;                /* product of sums */
        }
    }
    if (x > 1) sum *= x + 1;           /* if x > 1, then x is prime */
    return sum - n;
}
于 2013-09-19T01:58:12.253 回答
0

我在stackoverflow上回答了一个类似的问题

有一种执行速度更快的算法，它基于使用素因子分解的除数之和公式。

首先，您构建一个素数表，使最后一个素数平方小于您的数字的上限。然后将公式应用于每个条目。如果一个数字写成

n = a1^p1 * a1^p2 *... *an^pn

找到给定数字总和的复杂性n将是

p1+p2+...+pn = roughtly log(n)

这比O(sqrt(n))第一次优化的复杂性要好，因为它会提前停止循环

于 2013-09-16T20:38:24.720 回答
0

我将从根本不将数字存储在数组中开始。您不需要 - 只需读取值、处理它并输出结果。编译器很可能没有意识到n[i]整个循环中的值是相同的，并且没有其他任何东西可以修改它。

逻辑对我来说似乎不是很清楚。并且if (n[i] == 1) { sum = 1} else ...比设置更有意义sum = -1。

您也许还可以保留一份“共同因素”列表（http://en.wikipedia.org/wiki/Memoization），这样您就不必多次重新计算同一件事。[例如，如果你知道某事物的因数为 24，那么它也有 2、3、4、6 和 8。

于 2013-09-16T20:16:09.430 回答
0

此代码的复杂度为 O(n * log(n))。但是您可以以恒定的时间输出所需的答案。

int ans[500000 + 10], m = 500000;

int f(){
    for(int i = 1; i <= m; i++){
       for(int j = i + i; j <= m; j += i){
           ans[j] += i;
       }
     }
}

这里ans是一个数组，其中包含从 2 到 m 的适当除数之和。

于 2016-04-28T14:16:16.063 回答