c - 减少整数分数算法

Question

(来源于最近完成的一个编程竞赛)

在 1..10^7 范围内给你两个 10^5 整数数组:

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

假设有理数 X 是将 N 的所有元素相乘并除以 D 的所有元素的结果。

修改两个数组而不改变 X 的值(并且不分配任何超出范围的元素)，使得 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 次操作的解决方案？

Answer 1

因式分解 1 到 10 范围内的所有数字⁷。 使用埃拉托色尼筛法的改进版，您可以在 O(n*log n) 时间内分解从 1 到 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 中的数字，减法。

遍历 map ，如果素数的指数为正，则将 p^exponent 输入到数组 N(您可能需要将其拆分为多个索引，如果指数太大，对于小值，将几个素数合并到一个条目中 - 有 664579 个小于 10⁷ 的素数，因此数组中的 100,000 个槽可能不足以存储每个出现的素数使用正确的幂)，如果指数为负，则对 D 数组执行相同操作，如果为 0，则忽略该素数。

然后将 N 或 D 中任何未使用的槽位设置为 1。