减少整数级分算法

（这是从最近完成编程竞争衍生）减少整数级分算法

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

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

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

修改两个数组而不更改X的值（并且不指定任何元素超出范围），例如N的产物和D的产物没有共同点n因素。

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

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左右的解决方案？

来源

2012-09-10 Andrew Tomazos

http://stackoverflow.com/questions/12359785/reducing -integer-fractions-algorithm-solution-explanation –

不确定为什么您发布了带有答案链接的问题。 –

@RaymondChen：当我发布这个问题时，我没有解决方案代码，并且当我得到它时我不明白解决方案代码，因此发布了单独的问题以供解释并将它们相互关联。 –

Factorise所有数字范围在1到10之间。 ~~使用Eratosthenes筛的修改，你可以使用O(n*log log n)空间来分解所有数字，从1到n,O(n*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; 
      } 
     } 
    } 
}

要使用筛factorise一些n > 1，查找其最小素因子p，确定在n的因式分解它的多样性（通过递归查找，或者通过简单地将直到p不整除剩下的辅助因子，更快取决于）和辅因子。当辅助因子大于1时，查找下一个主要因素并重复。

通过两个阵列中N创建一个从素数的地图整数

围棋，每个号码在其因式分解在D添加的每个主要的指数的值在地图上，为数字，减去。

经过地图，如果主要的指数为正，进入p^exponent到阵列N（可能需要拆分跨多个指标，如果指数过大，而对于小的值，几个质数组合成一个条目 - 有664579个素数小于10 ，因此阵列中的100,000个插槽可能不足以存储具有正确功率的每个出现的素数），如果指数是负数，则与D阵列相同，如果它是0，则忽略该素数。

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

来源

2012-09-10 19:36:17

我知道如何使用Sieve来查找素数，但您如何使用它来查找素数分解？你有一个网站的参考？ –

而不是仅仅标记一个数字是否为复合数字，而是记录素数因子。实际上，对我来说，它可能更好 - 也更简单 - 只记录每个数字的最小素数因子，然后可以使用它递归地对两个数组中的数字进行因式分解。 Web引用，除非我可以链接到[一个Haskell实现]（http://hackage.haskell.org/packages/archive/arithmoi/0.4.0.3/doc/html/Math-NumberTheory-Primes- Factorisation.html＃v：factorSieve）这样一个最小的素因子筛。 –

找到质量因子分解（或绕过该操作）是问题的真正挑战。我认为这不是一件好事。 –

允许素比化的每一个元素的N & d在O（SQRT（10^7）* 10^5）

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-10 19:35:05

'O'表示法在这里感觉很奇怪。是否打算补偿3162至1000？ –

是的。更确切地说，它应该是O（sqrt（10^7）* 10^5），正如你所指出的那样。 –

只要问题中没有'O'符号，你就不能在答案中有实际意义。此外，整个输入是恒定的大小，因此整个计算必然是恒定的时间，换言之，“O（1）”操作，甚至没有考虑要解决的任务太多或关于确切的输入大小;只要它是恒定的。 –

分解数组，排序，取消的每个元素。因式分解对于有界大小的整数是恒定的，分类是n log n，并且抵消将是线性的。不过，常数因素可能很大。

如果您尝试的是较低的实际执行时间而不是较低的渐近复杂度，则可能不会通过手动取消诸如2,3,5和7的幂等小因素对阵列进行预处理。高概率（即病态输入除外），这将极大地加速大多数算法，代价是几次线性时间过程。

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

然后，对于N中的每个这样的整数，对于每个素数，将整数减小到该素数，直到它不再均匀分配为止，并且每次增加该素数的计数。对D做同样的事情，而不是递减。一旦你经历了素数表，当前的int将是非1，当且仅当它是大于3162的素数。这应该是每个阵列中总整数的约7％。你可以把它们保存在一堆或其他东西中。将它们设置为阵列中的一些，就像你一样。

最后，您遍历正面因素并将其产品纳入N.您可能需要将其分割到多个阵列插槽中，这很好。把负面因素纳入D，你就完成了！

运行时间会让我花一分钟解决问题。希望这是合理的。

来源

2012-09-10 19:48:13

几乎所有已被写入，我建议令P =
设q =（在d的所有元素的乘法）（以N的所有元素的乘法）
X =（P/Q）;应始终保持恒定
找到p，q的素因子;
可能存储在矩阵a [0]（2的幂），a [1]（3的幂），a [2]（5的幂）等等中的幂。现在您可以比较矩阵中的值并将较低的功率降至零。
例如。 p = 1280 q = 720
对于p a [0] = 8（幂2）a [1] = 0（幂3）a [2] = 1（幂5）;对于q b [0] = 4 b [1] = 2 b [2] = 1时的
;

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

来源

2012-09-11 07:20:21 k53sc

减少整数级分算法

回答

相关问题