9

（これは最近完了したプログラミングコンテストから派生しています）

1..10^7の範囲の10^5intの2つの配列が与えられます。

int N[100000] = { ... }
int D[100000] = { ... }

有理数Xが、Nのすべての要素を乗算し、Dのすべての要素で除算した結果であると想像してください。

Xの値を変更せずに（および範囲外の要素を割り当てずに）2つの配列を変更して、Nの積とDの積に共通の因子がないようにします。

素朴な解決策（私は思う）はうまくいくでしょう...

for (int i = 0; i < 100000; i++)
    for (int j = 0; j < 100000; j++)
    {
        int k = gcd(N[i], D[j]); // euclids algorithm

        N[i] /= k;
        D[j] /= k;
    }

...しかし、これは遅すぎます。

約10^9回未満の操作で済むソリューションとは何ですか？

4

4 に答える 4

3

1から107の範囲のすべての数値を因数分解します。エラトステネスのふるいの修正を使用すると、スペースを使用して1から時間までのすべての数値を因数分解できますn（O(n*log n)少し良いと思いますO(n*(log log n)²)）O(n*log log n)。それよりも優れているのは、おそらく最小の素因数の配列を作成することです。

// Not very optimised, one could easily leave out the even numbers, or also the multiples of 3
// to reduce space usage and computation time
int *spf_sieve = malloc((limit+1)*sizeof *spf_sieve);
int root = (int)sqrt(limit);
for(i = 1; i <= limit; ++i) {
    spf_sieve[i] = i;
}
for(i = 4; i <= limit; i += 2) {
    spf_sieve[i] = 2;
}
for(i = 3; i <= root; i += 2) {
    if(spf_sieve[i] == i) {
        for(j = i*i, step = 2*i; j <= limit; j += step) {
            if (spf_sieve[j] == j) {
                spf_sieve[j] = i;
            }
        }
    }
}

そのふるいを使用して数を因数分解するにはn > 1、最小の素因数pを調べ、因数分解の多重度を決定しnます（再帰的に調べるかp、残りの補因子が均等に分割されなくなるまで単純に除算することで、より高速に依存します）。補因子。補因子が1より大きい間、次の素因数を調べて繰り返します。

素数から整数へのマップを作成する

両方の配列をN調べ、の各数値について、因数分解の各素数の指数をマップの値に加算し、の数値についてDは減算します。

マップを確認し、素数の指数が正の場合p^exponent、配列に入力しNます（指数が大きすぎる場合は複数のインデックスに分割する必要があり、値が小さい場合は、複数の素数を1つのエントリに結合します-664579があります素数が107未満であるため、配列内の100,000スロットでは、表示される各素数を正しい累乗で格納するのに十分でない場合があります）、指数が負の場合はD配列で同じことを行い、0の場合はその素数を無視します。

Nまたはの未使用のスロットはD1に設定されます。

于 2012-09-10T19:36:17.830 に答える
1

O（sqrt（10 ^ 7）* 10 ^ 5）のN＆Dのすべての要素を次のように素数分解しましょう

N[i]=p1^kn1 * p2^kn2 ... 
D[i]=p1^kd1 * p2^kd2 ...

2つの電源アレイを維持する

Power_N[p1]=sum of kn1 for all i's
Power_D[p1]=sum of kd1 for all i's

Divide the N and D by p1^(min(Power_N[p1],Power_D[p2])) in O(10^5) each
于 2012-09-10T19:35:05.177 に答える
1

いずれかの配列の各要素を因数分解し、並べ替え、キャンセルします。因数分解は、制限されたサイズのintの定数時間であり、並べ替えはn log nであり、キャンセルは線形になります。ただし、定数係数は大きくなる可能性があります。

漸近的な複雑さを低くするのではなく、実際の実行時間を短くしようとしている場合は、2、3、5、7の累乗などの小さな要素を手動でキャンセルして、配列を前処理しても問題はないでしょう。病理学的入力を除いて）、これにより、ほとんどのアルゴリズムが大幅に高速化されますが、線形時間のパスが数回発生します。

上記のアプローチを統合するもう1つの洗練された方法は、までの素数のリストを作成することから始めることsqrt(10^7) ~= 3162です。3162/ln(3162) ~= 392素数定理によって、そのような素数についてあるはずです。（実際、実行時間を節約するために、このテーブルを事前に計算することができます/すべきです。）

次に、のそのような整数ごとN、および各素数について、整数が均等に分割されなくなるまでその素数だけ整数を減らし、そのたびにその素数のカウントをインクリメントします。の場合も同じようにしD、代わりにデクリメントします。素数の表を確認すると、3162より大きい素数である場合に限り、現在のintは1以外になります。これは、各配列の合計整数の約7％である必要があります。これらはヒープなどに保持できます。進むにつれて、それらも配列内のものに設定します。

最後に、正の要素を繰り返し処理し、それらの積をNに入れます。おそらくこれを複数のアレイスロットに分割する必要がありますが、これは問題ありません。負の要素をDに入れると、完了です。

この実行時間は、解決するのに1分かかります。うまくいけば、それは合理的です。

于 2012-09-10T19:48:13.450 に答える
0


ほとんどすべてが書かれています、私はp =（Nのすべての要素の乗算）let q =（Dのすべての要素の乗算）
X =（p / q）;を提案します。定数である必要があり、常に
p、qの素因数を見つけます。
おそらく、これらの累乗を行列a [0]（2の累乗）、a [1]（3の累乗）、a [2]（5の累乗）などに格納することによって。これで、行列の値を比較して、下の値の累乗をゼロに減らすことができます。
例えば。p = 1280 q = 720
for pa [0] = 8（2の累乗）a [1] = 0（3の累乗）a [2] = 1（5の累乗）;
qb [0] = 4 b [1] = 2 b [2]=1の場合;

インデックス0,1,2......の1つ/両方（両方が等しい場合）の値/秒をゼロにします。

于 2012-09-11T07:20:21.043 に答える