0

これは、この問題のフォローアップです。

整数分数アルゴリズムの削減

以下は、グランドマスターからの問題の解決策です。

#include <cstdio>
#include <algorithm>
#include <functional>

using namespace std;

const int MAXN = 100100;
const int MAXP = 10001000;

int p[MAXP];

void init() {
    for (int i = 2; i < MAXP; ++i) {
        if (p[i] == 0) {
            for (int j = i; j < MAXP; j += i) {
                p[j] = i;
            }
        }
    }
}

void f(int n, vector<int>& a, vector<int>& x) {
    a.resize(n);
    vector<int>(MAXP, 0).swap(x);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        for (int j = a[i]; j > 1; j /= p[j]) {
            ++x[p[j]];
        }
    }
}

void g(const vector<int>& v, vector<int> w) {
    for (int i: v) {
        for (int j = i; j > 1; j /= p[j]) {
            if (w[p[j]] > 0) {
                --w[p[j]];
                i /= p[j];
            }
        }
        printf("%d ", i);
    }
    puts("");
}

int main() {
    int n, m;
    vector<int> a, b, x, y, z;

    init();
    scanf("%d%d", &n, &m);
    f(n, a, x);
    f(m, b, y);
    printf("%d %d\n", n, m);
    transform(x.begin(), x.end(), y.begin(),
        insert_iterator<vector<int> >(z, z.end()),
        [](int a, int b) { return min(a, b); });
    g(a, z);
    g(b, z);

    return 0;
}

それがどのように機能するかは私にはわかりません。誰かがそれを説明できますか？

同等性は次のとおりです。

a is the numerator vector of length n
b is the denominator vector of length m
4

2 に答える 2

3

initの最大の素因数Pを含むように配列を埋めるだけです。P[i]i

f(n,a,x)xaの数が各素数で割り切れる回数で埋められ、累乗を複数回カウントします。事実上、それはの積の素因数分解を計算しますa。

g(v,w)数のリストとv素因数分解を取り、w共通の因子を共有しなくなるまで、vの要素をwの共通の因子で除算します。（素因数分解を除算することは、累乗を1で引くことを意味します）。

これで、ができmainました。まず、P配列を初期化し、データの長さを読み込みます（奇妙なことに、データ自体を読み込んでいるようには見えません）。次に、aとbの要素の積の素因数分解をそれぞれxとyに格納します。次に、ループ内でラムダ式を使用して、これら2つの因数分解の要素ごとの最小値を取り、最大公約数の因数分解を行います。最後に、aとbの要素をこの公約数で分割します。

于 2012-09-10T21:44:49.120 に答える
0

理解した：

p[i]はiの最高の素因数です

したがって、ループ：

for (int i = x; i > 1; i /= p[i])
{
    p[i] is prime factor of x;
}

xの素因数ごとに1回反復します。

その後、彼はそれを使用して素因数をカウントしています。

そして、それらを使用して、分子/分母の用語を適切に分割します。

于 2012-09-10T21:45:18.447 に答える