减少整数分数算法

Question

(这源于最近完成的编程竞赛)

您将获得两个10 ^ 5整数的数组,范围为1..10 ^ 7,包括:

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 7}范围内的所有数字进行因式分解。使用埃拉托色尼筛的改进版，您可以使用空间将所有数字从 1 分解到时间n上O(n*log n)（我认为这更好一点，O(n*(log log n)\xc2\xb2)左右）O(n*log log n)。比这更好的可能是创建一个仅包含最小质因数的数组。

\n\n

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

\n\n

要使用该筛子对数字进行因式分解n > 1，请查找其最小素因子p，确定其在因式分解中的重数n（通过递归查找，或简单地除以直到p不能均匀地除剩余的辅因子，这取决于速度）和辅因子。当辅因子大于 1 时，查找下一个素因子并重复。

\n\n

创建从素数到整数的映射

\n\n

遍历两个数组，对于 中的每个数字N，将其因式分解中每个素数的指数与映射中的值相加，对于 中的数字D，减去。

\n\n

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

\n\n

N或中任何未使用的插槽D都将设置为 1。

\n