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 中。然后它在循环中使用 lambda 表达式来取这两个分解中的元素最小值，给出最大公因子的分解。最后，它通过这个公因数将 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 的每个素因子迭代一次；

然后他用它来计算主要因素。

然后使用它们来划分适当的分子/分母项。

于 2012-09-10T21:45:18.447 回答