[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
見積もり: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; }
[ad_2]
コメント