大数相乘和比较

Question

我有一个问题： 有K行N个数字（32位），我必须选择乘积最大的那行。

主要问题在于N可以增加到20。 我尝试使用对数来解决这个问题：

ld sum = 0, max = 0;
int index = 0;

for(int i = 0; i < k; i ++) { // K lines
    sum = 0, c = 0;
    for(int j = 0; j < n; j ++) { // N numbers
        cin >> t;
        if(t < 0)
            c++; // If the number is less than 0 i memorize it

        if(t == 1 || t == -1) { // if numbers = 1 OR -1
            sum += 0.00000001; // Because log(1) = 0
            if(t == -1)
                c ++;
        }
        else if(t == 0) { // if some number is equal to zero then the sum is = 0
            sum = 0;
            break;
        }
        else {
            sum += log10(fabs(t));
        }
    }

    if(c % 2 == 1) // if c is odd than multiply by -1
        sum *= -1;

    if(sum >= max) { 
        max = sum;
        index = i;
    }
    if((sum - max) < eps) { // if sum is equal to max i'm also have to choose it
        max = sum;
        index = i;
    }
}
cout << index + 1 << endl;

这个程序在50%的测试用例中运行正常。有没有办法优化我的代码呢？

- Rasul

---

你的程序只有一半的时间能正常工作，但你想要优化它？先让它正常运行起来再说... - Borgleader

@Borgleader，抱歉我的英语不好，我找不到正确的话来表达。我只是想说，也许计算中存在错误，或者您可以分享一下我可以找到信息的链接，谢谢！ - Rasul

你试过直接在浮点数中相乘吗？在现代台式电脑的环境下，我们可以使用双精度算术，其范围远超过2^620。当然，为了得到精确的答案，你仍然需要使用多精度整数算术。 - doynax

尝试筛选 - 剔除包含至少一个因子为0的1的乘积。考虑质因数分解：对于每个质数和乘积保持计数。如果存在一个没有比_b_更大的计数且至少有一个较小的_a_，则剔除乘积_b。减去每个质数的最小计数。相乘并比较。 - greybeard

@greybeard http://www.e-olymp.com/en/problems/54 - Rasul

Answer 1

如果 t == -1，则将 c 增加两次。

- Mikkel Christiansen

Answer 2

如果你想避免使用大数库，你可以利用这个性质：如果你将b1和b2位的数字相乘，那么结果将会是b1+b2位长。

1. 所以只需将一行中所有乘数的位数总和相加

   • 并进行比较

   • 将结果记在某个数组中

     int bits(DWORD p) // 计算 p 中有多少位，DWORD 是 32 位无符号整数
         {
         DWORD m=0x80000000; int b=32;
         for (;m;m>>=1,b--)
          if (p>=m) break;
         return b;
         } 
     

2. 按结果位数降序对行进行索引排序

3. 如果排序后第一个位数也是最大值，则该行为答案
4. 如果您有多个最大值（多行具有相同的位数且也是最大值）
   • 那么只需要将它们相乘即可

现在是乘法

• 你应该一次性乘以所有最大行
• 每次所有子结果都可以被相同的质数整除
• 将它们除以它
• 这样结果将被截断到更少的位数
• 所以它应该适合64位值
• 你应该检查素数，直到sqrt(max value)
• 当你的最大值为32位时，请检查素数，直到65536
• 因此，您可以制作一个静态素数表来加速检查
• 而且没有必要检查比实际子结果更大的素数
• 如果您知道如何使用埃拉托斯特尼筛法，则可以极大地加速此过程
• 但是，您需要在每次除法后跟踪索引偏移，并使用周期筛选表，这有点复杂，但可行
• 如果您不检查所有素数，而只检查几个选择的素数
• 那么结果仍然可能溢出
• 因此，您也应该处理它（抛出一些错误之类的东西）
• 或者将所有子结果除以某个值，但这可能会使结果无效

另一种乘法方法

• 您还可以按值对乘数进行排序
• 并检查它们是否存在于所有最大行中
• 如果是，则将它们更改为一个（或从列表中删除）
• 这可以与先前的方法相结合

大数乘法

• 你可以自己实现大数乘法
• 结果最多为20*32=640位
• 因此，结果将是无符号整数数组（位宽为8、16、32等任何你喜欢的）
• 你也可以将数字作为字符串处理
• 在这里查看如何计算 C++中快速精确的大数平方
• 它还包含了乘法方法
• 以及在这里基于NTT的Schönhage-Strassen乘法在C++中
• 但对于像你这样的小数字来说，那会更慢
• 最后你需要比较结果
• 所以从MSW到LSW进行比较，哪一行有更大的数字就是最大行
• （MSW是最高有效字，LSW是最低有效字）

- Spektre

---

@Rasul 顺便说一下，bits(x)=ceil(log2(x))=ceil(log10(x)/log10(2))=ceil(ln(x)/ln(2))，因此它与您的方法类似，但仅适用于整数算术。 - Spektre

Answer 3

我认为这行代码肯定是错的：

if(c % 2 == 1) // if c is odd than multiply by -1
    sum *= -1;

如果您的产品在区间[0,1]内，则其对数将为负数，这将使它变为正数。我认为您应该将其分开处理。

- marom