主页 / 问题 / 977757
Accepted
golubtsoff
Asked:2020-05-04 11:32:48 +0000 UTC2020-05-04 11:32:48 +0000 UTC

是否可以在不直接计算的情况下评估大数乘积的结果？

  • 772

在 7-8 年级的奥林匹克题中，使用了序号10^18。数字本身在范围内long long (_int64)。在求解的过程中，您必须将两个相似尺寸的数字相乘，并将相似的产品相互比较。

也就是说，产品的结果可以是订单数10^36，并且这些结果必须相互比较。考虑到这是奥林匹克竞赛，我认为那里不允许使用第三方库来处理大量数据，而且从参与者的年龄来看，他们自己不太可能需要编写函数来处理有大量数字。

是否可以在不直接计算的情况下评估产品的结果，并将它们相互比较？

UPD。按要求Alexey Ten附上问题的扫描件 。在此处输入图像描述

c++

2 个回答

  1. Best Answer

    我们需要比较a1 * a2和b1 * b2 比较整数部分，如果它们相等，那么除以的余数a2 * b2 我们使用 (a * b) % (c * b) = (a % c) * b 这个事实

    int cmp(uint64 a1, uint64 a2, uint64 b1, uint64 b2) {
    if (a1 < a2) {
        std::swap(a1, a2);
    } 
    if (b1 < b2) {
        std::swap(b1, b2);
    } 

    if (a2 == 0 && b2 == 0) {
        return 0;
    }

    If (a2 == 0) {
        return -1;
    }

    if (b2 == 0) {
        return 1;
    } 

    auto div1 = a1 / b2;
    auto div2 = b1 / a2;
    if (div1 > div2) {
        return 1;
    } 
    if (div1 < div2) {
        return -1;
    }  
    return cmp(a1 % b2, a2, b1 % a2, b2);
}
    • 3

  2. 对于这样的估计，通常存在一个（单调递增的）对数函数。还有她的财产

    log(ab) = log(a) + log(b)

    单调增加意味着如果

    log(a) > log(b)

    然后和

    a > b

    （只要对数的底大于 1）。

    缺点 - 然而，这些是浮点数，这意味着存在准确性问题，如果ab它们cd 非常接近，对数可能无法给出完全准确的答案。这种情况下，最好做一个128位的乘法，真的很简单。

    PS 不是很主题，但这里有几个使用对数表示大值的问题，可能有助于您理解：这里和这里。

    PPS 并且对了，写一个128位的加/减/乘还是蛮简单的（除法比较复杂，不过好像不是条件要求的）。

    PPPS 我不确定他们在哪个班级学习对数 - 但如果一个人参加奥林匹克竞赛，他应该比通常的学校知识更多。

    • 2

相关问题