-1

次のコードを使用して、ビッグモッズの問題を解決しようとしていました。

#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 になり (ここまでは OK)、pow(10,2) を計算します ...そして、少なくとも私のマシンに私のコンパイラーを接続すると、これは 100 をわずかに下回ります。したがって、へのキャストliは 100 ではなく 99 を生成し、それから私たちは死んでしまいます。

中間値を出力するようにコードをインストルメント化することで、これをより詳細に検証しようとしましたが、面白いことに、浮動小数点演算の微妙な点が原因で、これは通常失敗します。(変数に中間値を保存すると、整数未満の値を正確な整数値に変換する余分な浮動小数点の丸めが行われる可能性があります。)

于 2016-04-13T11:04:55.223 に答える