给定三个数字 a、 b 和 M 哪里 1<=b，m<=10^6 和 “a” 可能非常大，包含多达 10^6 数字。任务是找到 （a^b）%m .
null
例如：
Input : a = 3, b = 2, m = 4Output : 1Explanation : (3^2)%4 = 9%4 = 1Input : a = 987584345091051645734583954832576, b = 3, m = 11Output: 10
这个问题基本上是基于模运算的。我们可以写作 （a^b）%m 像 （a%m）*（a%m）*（a%m）*……（a%m），b次 .以下是解决此问题的算法：
- 因为“a”非常大，所以将“a”读作字符串。
- 现在我们试着减少a。我们用m取a的模一次，即；ans=a%m，现在用这种方式 ans=a%m 介于整数范围1到10^6之间，即：；1<=a%m<=10^6。
- 现在乘以 ans 通过 b-1 乘以并同时取中间乘法结果与m的模，因为中间乘法 ans 可能超过整数的范围，将产生错误答案。
C++
// C++ program to find (a^b) mod m for a large 'a' #include<bits/stdc++.h> using namespace std; // utility function to calculate a%m unsigned int aModM(string s, unsigned int mod) { unsigned int number = 0; for (unsigned int i = 0; i < s.length(); i++) { // (s[i]-'0') gives the digit value and form // the number number = (number*10 + (s[i] - '0' )); number %= mod; } return number; } // Returns find (a^b) % m unsigned int ApowBmodM(string &a, unsigned int b, unsigned int m) { // Find a%m unsigned int ans = aModM(a, m); unsigned int mul = ans; // now multiply ans by b-1 times and take // mod with m for (unsigned int i=1; i<b; i++) ans = (ans*mul) % m; return ans; } // Driver program to run the case int main() { string a = "987584345091051645734583954832576" ; unsigned int b=3, m=11; cout << ApowBmodM(a, b, m); return 0; } |
JAVA
// Java program to find (a^b) mod m for a large 'a' public class GFG { // utility function to calculate a%m static int aModM(String s, int mod) { int number = 0 ; for ( int i = 0 ; i < s.length(); i++) { // (s[i]-'0') gives the digit // value and form the number number = (number * 10 ); int x = Character.getNumericValue(s.charAt(i)); number = number + x; number %= mod; } return number; } // Returns find (a^b) % m static int ApowBmodM(String a, int b, int m) { // Find a%m int ans = aModM(a, m); int mul = ans; // now multiply ans by b-1 times // and take mod with m for ( int i = 1 ; i < b; i++) ans = (ans * mul) % m; return ans; } // Driver code public static void main(String args[]) { String a = "987584345091051645734583954832576" ; int b = 3 , m = 11 ; System.out.println(ApowBmodM(a, b, m)); } } // This code is contributed by Sam007 |
Python3
# Python program to find (a^b) mod m for a large 'a' def aModM(s, mod): number = 0 # convert string s[i] to integer which gives # the digit value and form the number for i in range ( len (s)): number = (number * 10 + int (s[i])) number = number % m return number # Returns find (a^b) % m def ApowBmodM(a, b, m): # Find a%m ans = aModM(a, m) mul = ans # now multiply ans by b-1 times and take # mod with m for i in range ( 1 ,b): ans = (ans * mul) % m return ans # Driver program to run the case a = "987584345091051645734583954832576" b, m = 3 , 11 print (ApowBmodM(a, b, m)) |
C#
// C# program to find (a^b) mod m // for a large 'a' using System; class GFG { // utility function to calculate a%m static int aModM( string s, int mod) { int number = 0; for ( int i = 0; i < s.Length; i++) { // (s[i]-'0') gives the digit // value and form the number number = (number * 10 ); int x = ( int )(s[i] - '0' ); number = number + x; number %= mod; } return number; } // Returns find (a^b) % m static int ApowBmodM( string a, int b, int m) { // Find a%m int ans = aModM(a, m); int mul = ans; // now multiply ans by b-1 times // and take mod with m for ( int i = 1; i < b; i++) ans = (ans * mul) % m; return ans; } // Driver Code public static void Main() { string a = "987584345091051645734583954832576" ; int b=3, m=11; Console.Write(ApowBmodM(a, b, m)); } } // This code is contributed by Sam007 |
PHP
<?php // PHP program to find (a^b) // mod m for a large 'a' // utility function to // calculate a%m function aModM( $s , $mod ) { $number = 0; for ( $i = 0; $i < strlen ( $s ); $i ++) { // (s[i]-'0') gives the digit // value and form the number $number = ( $number * 10 + ( $s [ $i ] - '0' )); $number %= $mod ; } return $number ; } // Returns find (a^b) % m function ApowBmodM( $a , $b , $m ) { // Find a%m $ans = aModM( $a , $m ); $mul = $ans ; // now multiply ans by // b-1 times and take // mod with m for ( $i = 1; $i < $b ; $i ++) $ans = ( $ans * $mul ) % $m ; return $ans ; } // Driver code $a = "987584345091051645734583954832576" ; $b = 3; $m = 11; echo ApowBmodM( $a , $b , $m ); return 0; // This code is contributed by nitin mittal. ?> |
Javascript
<script> // JavaScript program to find (a^b) mod m // for a large 'a' // Utility function to calculate a%m function aModM(s, mod) { let number = 0; for (let i = 0; i < s.length; i++) { // (s[i]-'0') gives the digit // value and form the number number = (number * 10 ); let x = (s[i] - '0' ); number = number + x; number %= mod; } return number; } // Returns find (a^b) % m function ApowBmodM(a, b, m) { // Find a%m let ans = aModM(a, m); let mul = ans; // Now multiply ans by b-1 times // and take mod with m for (let i = 1; i < b; i++) ans = (ans * mul) % m; return ans; } // Driver Code let a = "987584345091051645734583954832576" ; let b = 3, m = 11; document.write(ApowBmodM(a, b, m)); // This code is contributed by souravghosh0416 </script> |
输出
10
时间复杂性： O（len（a）+b）
辅助空间： O（1）
有效方法： 上述乘法可以简化为 日志b 通过使用 快速模幂运算 其中，我们通过指数的二进制表示来计算结果 （b） .如果设定位为 1. 我们将base的当前值乘以result，并将每次递归调用的base值平方。
递归代码：
C++14
#include <bits/stdc++.h> using namespace std; typedef long long ll; // Reduce the number B to a small number // using Fermat Little ll MOD(string num, int mod) { ll res=0; for ( int i=0;i<num.length();i++) res=(res*10+num[i]- '0' )%mod; return res; } ll ModExponent(ll a,ll b,ll m) { ll result; if (a==0) return 0; else if (b==0) return 1; else if (b&1) { result=a%m; result=result*ModExponent(a,b-1,m); } else { result=ModExponent(a,b/2,m); result=((result*result)%m+m)%m; } return (result%m+m)%m; } int main() { // String input as b is very large string a = "987584345091051645734583954832576" ; // String input as b is very large ll b = 3; ll m = 11; ll remainderA = MOD(a,m); cout << ModExponent(remainderA, b, m); return 0; } |
输出
10
时间复杂性： O（len（a）+logb）
辅助空间： O（日志b）
节省空间的迭代代码：
C++14
// C++ program to find (a^b) mod m for a large 'a' #include<bits/stdc++.h> using namespace std; typedef long long ll; // utility function to calculate a%m and b%m ll aModM(string s, ll mod) { ll number = 0; for (ll i = 0; i < s.length(); i++) { // (s[i]-'0') gives the digit value and form // the number number = (number*10 + (s[i] - '0' )); number %= mod; } return number; } // Returns find (a^b) % m ll ApowBmodM(ll x, ll y,ll m) { ll res=1; while (y) { if (y&1) res=(res*x)%m; y=y>>1; x=((x*x)%m+m)%m; } return (res%m+m)%m; } // Driver program to run the case int main() { string a = "987584345091051645734583954832576" ; ll b=3; ll m=11; // Find a%m ll x=aModM(a,m); cout << ApowBmodM(x,b,m); return 0; } |
输出
10
时间复杂性： O（len（a）+logb）
辅助空间： O（1）
案例：当“a”和“b”都非常大时。
如果两种方法都适用，我们也可以实现相同的方法 “a” 和 “b” 非常大。如果是那样的话，我们会先采取行动 摩登派青年 用它 M 使用我们的 阿莫德 作用然后把它传给上面的人 ApowBmodM 递归或迭代函数，以获得所需的结果。
递归代码：
C++14
#include <bits/stdc++.h> using namespace std; typedef long long ll; // Reduce the number B to a small number // using Fermat Little ll MOD(string num, int mod) { ll res=0; for ( int i=0;i<num.length();i++) res=(res*10+num[i]- '0' )%mod; return res; } ll ModExponent(ll a,ll b,ll m) { ll result; if (a==0) return 0; else if (b==0) return 1; else if (b&1) { result=a%m; result=result*ModExponent(a,b-1,m); } else { result=ModExponent(a,b/2,m); result=((result%m)*(result%m))%m; } return (result%m+m)%m; } int main() { // String input as b is very large string a = "987584345091051645734583954832576" ; // String input as b is very large string b = "467687655456765756453454365476765" ; ll m = 1000000007; ll remainderA = MOD(a,m); ll remainderB = MOD(b,m); cout << ModExponent(remainderA, remainderB, m); return 0; } |
输出
546081867
时间复杂性： O（连（a）+连（b）+日志b）
辅助空间： O（日志b）
节省空间的迭代代码：
C++14
// C++ program to find (a^b) mod m for a large 'a' #include<bits/stdc++.h> using namespace std; typedef long long ll; // utility function to calculate a%m and b%m ll aModM(string s, ll mod) { ll number = 0; for (ll i = 0; i < s.length(); i++) { // (s[i]-'0') gives the digit value and form // the number number = (number*10 + (s[i] - '0' )); number %= mod; } return number; } // Returns find (a^b) % m ll ApowBmodM(string &a, string& b,ll m) { ll res=1; // Find a%m ll x = aModM(a,m); // Find b%m ll y = aModM(b,m); while (y) { if (y&1) res=(res*x)%m; y=y>>1; x=((x%m)*(x%m))%m; } return (res%m+m)%m; } // Driver program to run the case int main() { string a = "987584345091051645734583954832576" ; string b= "467687655456765756453454365476765" ; ll m=1000000007; cout << ApowBmodM(a,b,m); return 0; } |
输出
546081867
时间复杂性： O（连（a）+连（b）+日志b）
辅助空间： O（1）
本文由 沙申克·米什拉（古卢） 并通过 1999年 .如果你愿意 极客 如果你想投稿，你也可以用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
