整数分数约简算法

（这来源于最近完成的一次编程比赛）

给你两个 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 次操作的解决方案？

Factorise all numbers in the range 1 to 10⁷. Using a modification of a Sieve of Eratosthenes, you can factorise all numbers from 1 to n in O(n*log n) time (I think it's a bit better, O(n*(log log n)²) or so) using O(n*log log n) space. Better than that is probably creating an array of just the smallest prime factors.

// 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， 减去。

Go through the map, if the exponent of the prime is positive, enter p^exponent to the array N (you may need to split that across several indices if the exponent is too large, and for small values, combine several primes into one entry - there are 664579 primes less than 10⁷, so the 100,000 slots in the arrays may not be enough to store each appearing prime with the correct power), if the exponent is negative, do the same with the D array, if it's 0, ignore that prime.

任何未使用的插槽N or D然后设置为 1。