使用 mod 和 pow 计算大数

Question

我试图使用以下代码解决 mod 这个大问题。

#include<iostream>
#include<cmath>

using namespace std;

typedef long int li;

li m;
li mod(li b,li p)
{
    if(p==0)
        return 1;
    if(p%2==0)
    {
        return ((mod(b,p/2)%m)*mod(b,p/2)%m)%m;
        //return (li)pow(mod(b,p/2)%m,2)%m;
    }
    return (b%m*mod(b,p-1)%m)%m;
}

main()
{
    li b,p;
    while(cin>>b>>p>>m)
    {
        cout<<mod(b,p)<<endl;
    }
}

但它为 ((mod(b,p/2)%m)*mod(b,p/2)%m)%m 提供了不同的输出和 pow(mod(b,p/2)%m,2)%m.i 想知道它们是否相同，如果是，为什么给出不同的输出。

示例输入： 3个 18132 17

17 1765 3

2374859 3029382 36123

没有pow函数的输出： 13 2个 13195

使用 pow 函数输出： 1个 2个 31329

带有pow函数的测试代码

#include<iostream>
#include<cmath>
using namespace std;

typedef long int li;

li m;
li mod(li b,li p)
{
    if(p==0)
        return 1;
    if(p%2==0)
    {
        //return ((mod(b,p/2)%m)*mod(b,p/2)%m)%m;
        return (li)pow(mod(b,p/2)%m,2)%m;
    }
    return (b%m*mod(b,p-1)%m)%m;
}

main()
{
    li b,p;
    while(cin>>b>>p>>m)
    {
        cout<<mod(b,p)<<endl;
    }
}

Answer 1

您报告的答案 "without pow function" 是正确的答案，我认为您的代码没问题。所以我认为 您的问题出在您正在应用的测试中，而不是在您的 mod 平方指数函数中。

pow 函数对（双精度）浮点数进行运算，即使两个输入都是小整数，也不能保证给出准确的结果。你正在发生的事情是，在某个时候 pow 返回一个比整数小一点点的值，然后你将它转换为 long int 并得到一个比你小 1 的值 "should"，之后一切都错了。

例如，如果您使用您的代码计算 3^6 mod 17，那么在某一时刻它会得到 3^3 mod 17 = 10（到目前为止还可以），然后计算 pow (10,2) ... 而且，至少在我的编译器机器上，结果略小于 100。因此转换为 li 会产生 99 而不是 100，然后我们'死了。

我试图通过检测您的代码以输出中间值来更详细地验证这一点，但有趣的是，由于浮点运算的微妙之处，这通常会失败。（在变量中保存中间值可能会导致它进行额外的浮点舍入，从而将小于整数的值变成精确的整数值。）

使用 mod 和 pow 计算大数

Calculating big numbers with mod and pow

c++

cmath

pow

mod