0

剰余累乗のコードに何か問題があり、疑似コードの 2 つの異なるソースを使用して 3 回書いたにもかかわらず、問題を見つけることができません。SE 上の C++ での累乗剰余に関する他の質問を読みましたが、役に立ちませんでした。これが私の最後のコードで、私が思うより単純だが最適ではない方法で書かれています:

#include<iostream>
using namespace std;

// base ^ exponent mod modulus 
unsigned mulmod1(unsigned base, unsigned exponent, unsigned modulus) {
    int result = 1;
    while(exponent > 0){
        if(exponent % 2 == 1)
            result = (result * base) % modulus;
        exponent >>= 1;
        base = (base * base) % modulus;
    }
  return result;
}

int main(){

//9688563^45896 mod 71 = 30
//12^53 mod 7 = 3

cout<<mulmod1(9688563,45896 ,71)<<"\n";   //gives 10 instead of 30
cout<<mulmod1(12,53,7)<<"\n";             //gives correct answer 3

return 0;
}
4

1 に答える 1

4

関数への入力をサニタイズしてくださいmulmod1! unsignedお預かりできません9688563*9688563。これをmodulus * modulus正しく行うと、べき乗剰余を正しく実行するために保持できるデータ型 (およびもちろん入力数値) が必要なだけです。

于 2013-03-03T12:55:19.387 に答える