减少整数分数算法整数、算法、分数

2023-09-11 03:30:00 作者：人潮拥挤我需要你√

（这是从最近完成的编程竞赛来源）

(This is derived from a recently completed programming competition)

您给出的10 ^ 5整数两个数组的范围1..10 ^ 7包括：

You are given two arrays of 10^5 ints in the range 1..10^7 inclusive:

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

想象有理数X为相乘N个所有元素，并采用D的所有要素划分的结果。

Imagine the rational number X be the result of multiplying together all the elements of N and dividing by all the elements of D.

修改两个阵列，而不改变X的值（和不分配任何元素超出范围），使得N的产物和D的产物没有共同因子

Modify the two arrays without changing the value of X (and without assigning any element out of range) such that the product of N and the product of D have no common factor.

一个天真的解决方案，（我认为）会工作会...

A naive solution (I think) would work would be...

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;
    }

...但是这是太慢了。

...but this is too slow.

什么是一个解决方案，只需要不到约10 ^ 9操作？

What is a solution that takes less than around 10^9 operations?

推荐答案

Factorise范围内的所有号码1至10 7 。使用埃拉托色尼的筛的修改，你可以factorise 1的所有号码 N 在 O（N * log n）的时间（我认为这是一个好一点， O（N *（日志日志N）2）左右），使用 O（ N *日志日志N）的空间。比那还好很可能创造只是最小的质因数的数组。

Factorise all numbers in the range 1 to 107. 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;
            }
        }
    }
}

要factorise一些 N'GT; 1 使用筛，仰望它的最小素因子 P ，决定了其在 N （无论是通过查找递归，或者简单地划分到 P 不平均分配剩余的辅因子，这是更快依赖）和辅助因子。虽然辅助因子大于1，查找下一个主要因素，并重复。


To factorise a number n > 1 using that sieve, look up its smallest prime factor p, determine its multiplicity in the factorisation of n (either by looking up recursively, or by simply dividing until p doesn't evenly divide the remaining cofactor, which is faster depends) and the cofactor. While the cofactor is larger than 1, look up the next prime factor and repeat.
从创建一个素数映射到整数
Create a map from primes to integers

穿过两个数组，在 N 每一个数字，在 D ，减去。

Go through both arrays, for each number in N, add the exponent of each prime in its factorisation to the value in the map, for the numbers in D, subtract.

穿过地图上，如果主要的指数为正，输入点^指数到数组 N （您可能需要分割跨越多个索引如果指数过大，和为小的值，将几个素数成一个条目 - 有664579素数小于10 7 ，所以100000槽在阵列可能不足以存储每个出现黄金与正确的功率），如果指数为负，做同样的 D 阵列，如果是0，忽略该素数。

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 107, 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中的任未使用的插槽或 D ，然后设置为1。