1


自然数 n (1 <= n <= 500000) が与えられた場合、すべての適切な約数の合計を出力してください。

定義: 自然数の適切な約数は、その数よりも厳密に小さい約数です。

たとえば、数値 20 には 1、2、4、5、10 の 5 つの適切な除数があり、除数の合計は 1 + 2 + 4 + 5 + 10 = 22 です。

入力

テスト ケースの数 (約 200000 に等しい) を示す整数と、1 ～ 500000 の範囲の 1 つの整数を含む多数の行が続きます。

出力

各行に 1 つの整数: それぞれ与えられた整数の除数の合計。

例

サンプル入力:

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

すぐに終了するように、以下のコードを更新しました。1 から 500,000 までのすべての整数に対して実行すると、-O3 を指定して Apple GCC 4.2.1 でコンパイルされた MacBookPro6,1 (2.66 GHz Intel Core i7) で 0.5 秒未満かかります。

ウィキペディア ページのプロパティ セクションにある除数関数の式 σ x ( n ) を使用します。事前に計算された素数のリストを使用すると、高速化できます。(最大 500,000 の入力をサポートするには 126 が必要であり、これにより時間が 4 分の 1 秒未満に短縮されます。) また、コードが少し乱雑になるという代償を払って、削除できる分割もいくつかあります。

//  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

私はstackoverflowの同様の質問に答えました

素因数分解を使用した除数の和の式に基づく、より高速に実行されるアルゴリズムがあります。

最初に、最後の素数の 2 乗が数値の上限より小さくなるように素数表を作成します。次に、式を各エントリに適用します。数字を次のように書くと

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

与えられた数の和を求める複雑さnは

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

O(sqrt(n))これは、ループを早期に停止する最初の最適化の複雑さよりも優れています

于 2013-09-16T20:38:24.720 に答える
0

素数を比較的迅速に計算する方法があるとします。これは、最大の入力値の平方根によって制限される、1 回限りの前払いアクティビティである可能性があります。この場合、最大の入力値 (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);

ここで、素数から、入力値ごとに次のことができます。

  • 素因数分解を計算する
  • 各素因数の累乗の和の積を計算します。

これにより、除数の合計が得られます。合計から入力値を減算して、適切な除数の合計を取得します。これらの 2 つの手順は、1 つのループに組み合わせることができます。

このアルゴリズムが機能するのは、多項式を乗算すると、乗算された多項式項のすべての組み合わせの合計が自然に得られるためです。各多項式の項が入力を分割する素数の累乗で構成される場合、乗算された項の組み合わせが除数を構成します。このアルゴリズムは高速で、[1, 500000] の間隔で 500000 の数値を Core i3 以上のプロセッサで 1 秒未満で処理できるはずです。

次の関数は、上記のメソッドを実装します。

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 に答える