Пронађите (а^б)%м где је 'а' веома велико
Пробајте на ГфГ пракси 
#працтицеЛинкДив { дисплаи: ноне !импортант; }
Излаз
Излаз
Излаз
Излаз
Излаз
#працтицеЛинкДив { дисплаи: ноне !импортант; } Задата три броја а б и м где 1 <=bm <=10^6 и 'а' може бити веома велика и садржи до 10^6 цифре. Задатак је пронаћи (а^б)%м .
Примери:
Input : a = 3 b = 2 m = 4 Output : 1 Explanation : (3^2)%4 = 9%4 = 1 Input : a = 987584345091051645734583954832576 b = 3 m = 11 Output: 10Recommended Practice Пронађите (а^б)%м Покушајте!
Овај проблем је у основи заснован на модуларној аритметици. Можемо писати (а^б) % м као (а%м) * (а%м) * (а%м) * ... (а%м) б пута . Испод је алгоритам за решавање овог проблема:
- Пошто је 'а' веома велико, читајте 'а' као стринг.
- Сада покушавамо да смањимо 'а'. Узимамо модул од 'а' по м једном, тј. анс = а % м на овај начин сада анс=а%м лежи између целог опсега од 1 до 10^6, тј. 1 <= a%m <= 10^6.
- Сада помножите године би б-1 пута и истовремено узети мод средњег резултата множења са м јер средње множење године може премашити опсег целог броја и даће погрешан одговор.
// C++ program to find (a^b) mod m for a large 'a' #include 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 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
Временска сложеност: О(само(а)+б)
Помоћни простор: О(1)
Ефикасан приступ: Горња множења се могу свести на лог б коришћењем брза модуларна експоненцијација где резултат израчунавамо бинарним приказом експонента (б) . Ако је постављени бит 1 множимо тренутну вредност базе да бисмо добили резултат и квадрирамо вредност базе за сваки рекурзивни позив.
Рекурзивни код:
C++14 // C++ program to find (a^b) mod m for a large 'a' with an // efficient approach. #include 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 ; }
Java // Java program to find (a^b) mod m for a large 'a' with an // efficient approach. public class GFG { // Reduce the number B to a small number // using Fermat Little static long MOD ( String num long mod ) { long res = 0 ; for ( int i = 0 ; i < num . length (); i ++ ) { res = ( res * 10 + num . charAt ( i ) - '0' ) % mod ; } return res ; } // Calculate the ModExponent of the given large number // 'a' static long ModExponent ( long a long b long m ) { long result ; if ( a == 0 ) { return 0 ; } else if ( b == 0 ) { return 1 ; } else if ( b % 2 != 0 ) { 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 ; } public static void main ( String [] args ) { // String input as a is very large String a = '987584345091051645734583954832576' ; long b = 3 ; long m = 11 ; long remainderA = MOD ( a m ); System . out . println ( ModExponent ( remainderA b m )); } } // The code is contributed by Gautam goel (gautamgoel962)
Python3 # Python3 program to find (a^b) mod m # for a large 'a' # Utility function to calculate a%m def MOD ( s mod ): res = 0 for i in range ( len ( s )): res = ( res * 10 + int ( s [ i ])) % mod return res # Returns find (a^b) % m def ModExponent ( a b m ): if ( a == 0 ): return 0 elif ( b == 0 ): return 1 elif ( b % 2 != 0 ): 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 # Driver Code a = '987584345091051645734583954832576' b = 3 m = 11 remainderA = MOD ( a m ) print ( ModExponent ( remainderA b m )) # This code is contributed by phasing17
C# // C# program to find (a^b) mod m for a large 'a' with an // efficient approach. using System ; using System.Collections.Generic ; public class GFG { // Reduce the number B to a small number // using Fermat Little static long MOD ( string num long mod ) { long res = 0 ; for ( int i = 0 ; i < num . Length ; i ++ ) { res = ( res * 10 + num [ i ] - '0' ) % mod ; } return res ; } // Calculate the ModExponent of the given large number // 'a' static long ModExponent ( long a long b long m ) { long result ; if ( a == 0 ) { return 0 ; } else if ( b == 0 ) { return 1 ; } else if ( b % 2 != 0 ) { 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 ; } // Driver Code public static void Main ( string [] args ) { // String input as a is very large string a = '987584345091051645734583954832576' ; long b = 3 ; long m = 11 ; // Function Call long remainderA = MOD ( a m ); Console . WriteLine ( ModExponent ( remainderA b m )); } } // The code is contributed by phasing17
JavaScript < script > // JavaScript program to find (a^b) mod m // for a large 'a' // Utility function to calculate a%m function MOD ( s mod ) { var res = 0 ; for ( var i = 0 ; i < s . length ; i ++ ) { res = ( res * 10 + ( s [ i ] - '0' )) % mod ; } return res ; } // Returns find (a^b) % m function ModExponent ( a b m ) { var result ; if ( a == 0 ) { return 0 ; } else if ( b == 0 ) { return 1 ; } else if ( b % 2 != 0 ) { 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 ; } // Driver Code let a = '987584345091051645734583954832576' ; let b = 3 m = 11 ; var remainderA = MOD ( a m ); document . write ( ModExponent ( remainderA b m )); // This code is contributed by shinjanpatra. < /script>
Излаз
10
Временска сложеност: О(лен(а)+ лог б)
Помоћни простор: О(логб)
Просторно ефикасан итеративни код:
C++14 // C++ program to find (a^b) mod m for a large 'a' #include 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 ; }
Java // Java program to find (a^b) mod m for a large 'a' import java.util.* ; class GFG { // utility function to calculate a%m and b%m static long aModM ( String s long mod ) { long number = 0 ; for ( int i = 0 ; i < s . length (); i ++ ) { // (s[i]-'0') gives the digit value and form // the number number = ( number * 10 + ( s . charAt ( i ) - '0' )); number %= mod ; } return number ; } // Returns find (a^b) % m static long ApowBmodM ( long x long y long m ) { long res = 1 ; while ( y > 0 ) { if (( y & 1 ) != 0 ) res = ( res * x ) % m ; y = y >> 1 ; x = (( x * x ) % m + m ) % m ; } return ( res % m + m ) % m ; } // Driver program to run the case public static void main ( String [] args ) { String a = '987584345091051645734583954832576' ; long b = 3 ; long m = 11 ; // Find a%m long x = aModM ( a m ); System . out . println ( ApowBmodM ( x b m )); } } // This code is contributed by phasing17
Python3 # Python3 program to find (a^b) mod m for a large 'a' # utility function to calculate a%m and b%m def aModM ( s mod ): number = 0 ; for i in range ( len ( s )): # int(s[i]) gives the digit value and form # the number number = ( number * 10 + int ( s [ i ])); number %= mod ; return number ; # Returns find (a^b) % m def ApowBmodM ( x y m ): res = 1 ; while ( y > 0 ): 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 a = '987584345091051645734583954832576' ; b = 3 ; m = 11 ; # Find a%m x = aModM ( a m ); print ( ApowBmodM ( x b m )); # This code is contributed by phasing17
C# // C# program to find (a^b) mod m for a large 'a' using System ; class GFG { // utility function to calculate a%m and b%m static long aModM ( string s long mod ) { long number = 0 ; for ( 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 static long ApowBmodM ( long x long y long m ) { long res = 1 ; while ( y > 0 ) { if (( y & 1 ) != 0 ) res = ( res * x ) % m ; y = y >> 1 ; x = (( x * x ) % m + m ) % m ; } return ( res % m + m ) % m ; } // Driver program to run the case public static void Main ( string [] args ) { string a = '987584345091051645734583954832576' ; long b = 3 ; long m = 11 ; // Find a%m long x = aModM ( a m ); Console . WriteLine ( ApowBmodM ( x b m )); } } // This code is contributed by phasing17
JavaScript // JavaScript program to find (a^b) mod m for a large 'a' // utility function to calculate a%m and b%m function aModM ( s mod ) { let number = 0 ; for ( var i = 0 ; i < s . length ; i ++ ) { // parseInt(s[i]) gives the digit value and form // the number number = ( number * 10 + parseInt ( s [ i ])); number %= mod ; } return number ; } // Returns find (a^b) % m function ApowBmodM ( x y m ) { let 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 let a = '987584345091051645734583954832576' ; let b = 3 ; let m = 11 ; // Find a%m let x = aModM ( a m ); console . log ( ApowBmodM ( x b m )); // This code is contributed by phasing17
Излаз
10
Временска сложеност: О(лен(а)+ лог б)
Помоћни простор: О(1)
Случај: Када су и 'а' и 'б' веома велики.
Такође можемо применити исти приступ ако оба 'а' и 'б' била веома велика. У том случају бисмо прво узели против од тога са м користећи наше аМодМ функција. Затим га пренесите на горе АповБмодМ рекурзивна или итеративна функција да би се добио тражени резултат.
Рекурзивни код:
C++14 #include 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 ; }
Java /*package whatever //do not write package name here */ import java.io.* ; class GFG { // Reduce the number B to a small number // using Fermat Little. static long MOD ( String num int mod ) { long res = 0 ; for ( int i = 0 ; i < num . length (); i ++ ) { res = ( res * 10 + num . charAt ( i ) - '0' ) % mod ; } return res ; } static long ModExponent ( long a long b long m ){ long result = 0 ; if ( a == 0 ) return 0 ; else if ( b == 0 ) return 1 ; else if (( b & 1 ) == 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 ; } public static void main ( String [] args ) { // String input as b is very large String a = '987584345091051645734583954832576' ; // String input as b is very large String b = '467687655456765756453454365476765' ; int m = 1000000007 ; long remainderA = MOD ( a m ); long remainderB = MOD ( b m ); System . out . println ( ModExponent ( remainderA remainderB m )); } } // This code is contributed by aadityapburujwale
Python3 # Python3 program to implement the approach # Reduce the number B to a small number # using Fermat Little def MOD ( num mod ): res = 0 ; for i in range ( len ( num )): res = ( res * 10 + int ( num [ i ])) % mod ; return res ; def ModExponent ( a b m ): if ( a == 0 ): return 0 ; elif ( b == 0 ): return 1 ; elif ( b & 1 ): result = a % m ; result = result * ModExponent ( a b - 1 m ); else : b = b // 2 result = ModExponent ( a b m ); result = (( result % m ) * ( result % m )) % m ; return ( result % m + m ) % m ; # String input as b is very large a = '987584345091051645734583954832576' ; # String input as b is very large b = '467687655456765756453454365476765' ; m = 1000000007 ; remainderA = ( MOD ( a m )); remainderB = ( MOD ( b m )); print ( ModExponent ( remainderA remainderB m )); # This code is contributed by phasing17
C# // C# program to implement the approach using System ; using System.Collections.Generic ; class GFG { // Reduce the number B to a small number // using Fermat Little. static long MOD ( string num int mod ) { long res = 0 ; for ( int i = 0 ; i < num . Length ; i ++ ) { res = ( res * 10 + num [ i ] - '0' ) % mod ; } return res ; } static long ModExponent ( long a long b long m ) { long result = 0 ; if ( a == 0 ) return 0 ; else if ( b == 0 ) return 1 ; else if (( b & 1 ) == 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 ; } public static void Main ( string [] args ) { // String input as b is very large string a = '987584345091051645734583954832576' ; // String input as b is very large string b = '467687655456765756453454365476765' ; int m = 1000000007 ; long remainderA = MOD ( a m ); long remainderB = MOD ( b m ); Console . WriteLine ( ModExponent ( remainderA remainderB m )); } } // This code is contributed by phasing17
JavaScript // JavaScript program to implement the approach // Reduce the number B to a small number // using Fermat Little function MOD ( num mod ) { let res = 0 ; for ( var i = 0 ; i < num . length ; i ++ ) res = ( res * 10 + parseInt ( num [ i ])) % mod ; return res ; } function ModExponent ( a b m ) { let result ; if ( a == 0n ) return 0n ; else if ( b == 0n ) return 1n ; else if ( b & 1n ) { result = a % m ; result = result * ModExponent ( a b - 1n m ); } else { b = b / 2n - ( b % 2n ); result = ModExponent ( a b m ); result = (( result % m ) * ( result % m )) % m ; } return ( result % m + m ) % m ; } // String input as b is very large let a = '987584345091051645734583954832576' ; // String input as b is very large let b = '467687655456765756453454365476765' ; let m = 1000000007 ; let remainderA = BigInt ( MOD ( a m )); let remainderB = BigInt ( MOD ( b m )); console . log ( ModExponent ( remainderA remainderB BigInt ( m ))); // This code is contributed by phasing17
Излаз
546081867
Временска сложеност: О(лен(а)+лен(б)+лог б)
Помоћни простор: О(логб)
Просторно ефикасан итеративни код:
C++14 // C++ program to find (a^b) mod m for a large 'a' #include 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 ; }
Java /*package whatever //do not write package name here */ import java.io.* ; class GFG { // utility function to calculate a%m and b%m static long aModM ( String s long mod ){ long number = 0 ; for ( int i = 0 ; i < s . length (); i ++ ) { // (s.charAt(i)-'0') gives the digit value and form // the number number = ( number * 10 + ( s . charAt ( i ) - '0' )); number %= mod ; } return number ; } // Returns find (a^b) % m static long ApowBmodM ( String a String b long m ) { long res = 1 ; // Find a%m long x = aModM ( a m ); // Find b%m long y = aModM ( b m ); while ( y > 0 ) { if (( y & 1 ) == 1 ) res = ( res * x ) % m ; y = y >> 1 ; x = (( x % m ) * ( x % m )) % m ; } return ( res % m + m ) % m ; } public static void main ( String [] args ) { String a = '987584345091051645734583954832576' ; String b = '467687655456765756453454365476765' ; long m = 1000000007 ; System . out . println ( ApowBmodM ( a b m )); } } // This code is contributed by aadityapburujwale
Python3 # Python3 program to find (a^b) mod m for a large 'a' # utility function to calculate a%m and b%m def aModM ( s mod ): number = 0 for i in range ( len ( s )): # (s[i]-'0') gives the digit value and form # the number number = ( number * 10 + ( int ( s [ i ]))) number %= mod return number # Returns find (a^b) % m def ApowBmodM ( a b m ): res = 1 # Find a%m x = aModM ( a m ) # Find b%m y = aModM ( b m ) while ( y > 0 ): 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 a = '987584345091051645734583954832576' b = '467687655456765756453454365476765' m = 1000000007 print ( ApowBmodM ( a b m )) # This code is contributed by phasing17
JavaScript // JavaScript program to find (a^b) mod m for a large 'a' // utility function to calculate a%m and b%m function aModM ( s mod ) { let number = 0n ; for ( let i = 0 ; i < s . length ; i ++ ) { // (s[i]-'0') gives the digit value and form // the number number = ( number * 10n + BigInt ( parseInt ( s [ i ]))); number %= mod ; } return number ; } // Returns find (a^b) % m function ApowBmodM ( a b m ) { let res = 1n ; // Find a%m let x = BigInt ( aModM ( a m )); // Find b%m let y = BigInt ( aModM ( b m )); while ( y > 0n ) { if ( y & 1n ) res = ( res * x ) % m ; y = y >> 1n ; x = (( x % m ) * ( x % m )) % m ; } return ( res % m + m ) % m ; } // Driver program to run the case let a = '987584345091051645734583954832576' ; let b = '467687655456765756453454365476765' ; let m = 1000000007n ; console . log ( ApowBmodM ( a b m )); // This code is contributed by phasing17
C# // C# program to find (a^b) mod m for a large 'a' using System ; using System.Collections.Generic ; class GFG { // utility function to calculate a%m and b%m static long aModM ( string s long mod ) { long number = 0 ; for ( 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 static long ApowBmodM ( string a string b long m ) { long res = 1 ; // Find a%m long x = aModM ( a m ); // Find b%m long y = aModM ( b m ); while ( y != 0 ) { if (( y & 1 ) != 0 ) res = ( res * x ) % m ; y = y >> 1 ; x = (( x % m ) * ( x % m )) % m ; } return ( res % m + m ) % m ; } // Driver program to run the case public static void Main ( string [] args ) { string a = '987584345091051645734583954832576' ; string b = '467687655456765756453454365476765' ; long m = 1000000007 ; Console . WriteLine ( ApowBmodM ( a b m )); } } // This code is contributed by phasing17
Излаз
546081867
Временска сложеност: О(лен(а)+лен(б)+ лог б)
Помоћни простор: О(1)
Ако желите ГеексфорГеекс и желите да допринесете, такође можете написати чланак користећи врите.геексфоргеекс.орг или пошаљите свој чланак на адресу ревиев-теам@геексфоргеекс.орг.
