用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（a，p/2。

样本输入：3.1813217

1717653

2374859302938236123

不带pow功能的输出：132.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

您报告的"没有pow函数"的答案是正确的答案，您的代码在我看来还可以。所以我认为您的问题在于您正在应用的测试，而不是您的模幂函数。

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

例如，如果你用代码计算3^6 mod 17，那么在某一点上它得到3^3 mod 17=10（到目前为止还可以），然后计算pow（10,2）。。。而且，至少在我的编译器机器上，这只会比100少一点。所以li的强制值是99而不是100，然后我们就死了。

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