-1

我试图使用以下代码解决大 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)% 提供不同的输出我想知道它们是否不同，如果它们是不同的输出的原因。

样本输入：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;
    }
}
4

1 回答 1

0

您报告的“没有 pow 功能”的答案是正确的答案，您的代码对我来说看起来不错。所以我认为你的问题在于你正在应用的测试，而不是你的模幂函数。

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

例如，如果您使用代码计算 3^6 mod 17，那么在某一时刻它会得到 3^3 mod 17 = 10（到目前为止还可以），然后计算 pow(10,2) ...并且，至少在我的机器和我的编译器，结果只是比 100 少一点。所以转换为li99 而不是 100，然后我们就死了。

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

于 2016-04-13T11:04:55.223 回答