【解決方法】力(a、b)が正常に機能しない

プログラミングQA

2022.11.28

[ad_1]

質問：

あなたの仕事は、値 a^b modulo 10^9+7 を効率的に計算することです。

このタスクでは、0^0=1 と仮定していることに注意してください。

10^9 + 7 を法とする行が何を伝えたいのか理解できません。
A(power)B の私のプログラムは、大きな出力値に対して機能していないと思います..
しかし、出力値が小さい場合は正しく機能しています..

私が試したこと：

ヘッダ

#include <bits/stdc++.h>
#define MOD 1000000007;
using namespace std;

long long int power(long long int n,int x);

主な機能

int main (){
    int T;
    cin >> T;       // no. of testcases..
    for(int i = 0 ; i < T ; i++){       // running the loop for T no. of testcases
        long long int n;
        int x;
        cin >> n;
        cin >> x;
        cout << power(n,x) << '\n';
    }
}

パワー機能

long long int power(long long int n,int x){
long long int res = 1;
    while(x){
        if(x%2 == 0){
            n = n*n;
            x = x/2;
        }
        else{
            res = res*n;
            x--;
        }
    }
    res = res%MOD;
    return res;
}

入力：

3(Test_Cases)
3 4
2 8
123 123

期待される出力

81
256
921450052

受信出力

81
256
522397166

解決策 1
解決策 2
解決策 3

解決策 1

見積もり：

10^9 + 7 を法とする行が何を伝えたいのか理解できません。

オーバーフローからあなたを守ります 64-ビット整数、理由:

(A * B) mod C = (A mod C * B mod C) mod C

(たとえば、剰余乗算>[^]）。

試す

C++

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

uint32_t powermod(uint32_t a, uint32_t b)
{
  constexpr uint32_t MOD = 1E9+7;

  uint64_t result = 1;
  while ( b--)
  {
    result *= a;
    result %= MOD;
  }
  return static_cast<uint32_t>(result);
}
int main()
{
  uint32_t a[][2]{ {3, 4}, {2, 8}, {123, 123} };


  for ( auto p : a)
  {
    cout << "powermod(" << p[0] << ", " << p[1] << ") = " << powermod(p[0],p[1])<< "\n";
  }

}

解決策 2

long long int power(long long int n,int x){
long long int res = 1;
    while(x){
        if(x%2 == 0){
            n = n*n;
            n = n%MOD;
            x = x/2;
        }
        else{
            res = res*n;
            res = res%MOD;
            x--;
        }
    }
    return res;
}

解決策 3

最初の解決策を読んだ後の私の更新されたコード

long long int power(long long int n,int x){
long long int res = 1;
    while(x){
        if(x%2 == 0){
            n = n*n;
            n = n%MOD;
            x = x/2;
        }
        else{
            res = res*n;
            res = res%MOD;
            x--;
        }
    }
    return res;
}