9

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

在 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 次操作的解决方案是什么？

4

4 回答 4

3

因式分解 1 到 10 7范围内的所有数字。使用对 Eratosthenes 筛的修改，您可以使用空间将所有数字从 1 分解到n时间O(n*log 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，减去。

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

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

于 2012-09-10T19:36:17.830 回答
1

让我们将 O(sqrt(10^7) * 10^5) 中 N 和 D 中的每个元素分解为

N[i]=p1^kn1 * p2^kn2 ... 
D[i]=p1^kd1 * p2^kd2 ...

维护 2 个电源阵列，其中

Power_N[p1]=sum of kn1 for all i's
Power_D[p1]=sum of kd1 for all i's

Divide the N and D by p1^(min(Power_N[p1],Power_D[p2])) in O(10^5) each
于 2012-09-10T19:35:05.177 回答
1

分解任一数组的每个元素，排序，取消。对于有界大小的整数，因式分解是常数时间，排序是 n log n，取消将是线性的。不过，常数因子可能很大。

如果您尝试降低实际执行时间而不是降低渐近复杂度，那么通过手动取消小因素（例如 2、3、5 和 7 的幂）来预处理数组可能不会有什么坏处。概率很高（即除了病态输入），这将极大地加速大多数算法，但代价是一些线性时间通过。

一种更复杂的方法，整合上述方法，将首先建立一个质数列表，直到sqrt(10^7) ~= 3162. 应该有3162/ln(3162) ~= 392这样的素数，由素数定理。（事实上​​，为了节省运行时间，您可以/应该预先计算此表。）

然后，对于 中的每个这样的整数N和每个素数，将整数减去那个素数，直到它不再均匀除，并且每次增加那个素数的计数。对 做同样的事情D，而是递减。一旦你浏览了素数表，当且仅当它是大于 3162 的素数时，当前 int 将是非 1。这应该是每个数组中总整数的 7% 左右。你可以把它们放在一堆或类似的地方。随着您的进行，也将它们设置为数组中的那些。

最后，您迭代正因子并将它们的乘积放入 N。您可能需要将其拆分到多个数组槽中，这很好。将负面因素放入D，你就完成了！

这方面的运行时间需要我一分钟来解决。希望这是合理的。

于 2012-09-10T19:48:13.450 回答
0

几乎所有的东西都写好了，我建议让 p=(N
中所有元素的乘法) 让 q=(D 中所有元素的乘法)
X=(p/q); 应该是常数总是
找到 p,q 的素数；
通过可能将他们的幂存储在矩阵 a[0]（2 的幂）、a[1]（3 的幂）、a[2]（5 的幂）等中。现在您可以比较矩阵中的值并将较低的一的幂降低到零。
例如。p=1280 q=720
for pa[0]=8（2 的幂） a[1]=0（3 的幂） a[2]=1（5 的幂）；
对于 qb[0]=4 b[1]=2 b[2]=1;

使索引 0,1,2 的一个/两个（如果两者相等）值/s 为零.......

于 2012-09-11T07:20:21.043 回答