Poiščite (a^b)%m, kjer je 'a' zelo velik
Preizkusite na GfG Practice 
#practiceLinkDiv { display: none !important; }
Izhod
Izhod
Izhod
Izhod
Izhod
#practiceLinkDiv { display: none !important; } Podane tri številke a b in m kjer 1 <=bm <=10^6 in 'a' je lahko zelo velik in vsebuje do 10^6 števke. Naloga je najti (a^b)%m .
Primeri:
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 Poišči (a^b)%m Poskusite!
Ta problem v osnovi temelji na modularni aritmetiki. Lahko pišemo (a^b) % m kot (a%m) * (a%m) * (a%m) * ... (a%m) b-krat . Spodaj je algoritem za rešitev te težave:
- Ker je 'a' zelo velik, preberite 'a' kot niz.
- Zdaj poskušamo zmanjšati 'a'. Enkrat vzamemo modul 'a' z m, tj. ans = a % m na ta način zdaj ans=a%m leži med celim obsegom od 1 do 10^6, tj. 1 <= a%m <= 10^6.
- Zdaj pa pomnožite leta avtor b-1 krat in hkrati vzamemo mod vmesnega množenja rezultat z m, ker vmesno množenje leta lahko preseže obseg celega števila in bo povzročil napačen odgovor.
// 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>
Izhod
10
Časovna zapletenost: O(samo(a)+b)
Pomožni prostor: O(1)
Učinkovit pristop: Zgornja množenja je mogoče zmanjšati na dnevnik b z uporabo hitro modularno potenciranje kjer izračunamo rezultat z binarno predstavitvijo eksponenta (b) . Če je nastavljeni bit 1 pomnožimo trenutno vrednost osnove za rezultat in kvadriramo vrednost osnove za vsak rekurzivni klic.
Rekurzivna koda:
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>
Izhod
10
Časovna zapletenost: O(len(a)+ log b)
Pomožni prostor: O(logb)
Prostorsko učinkovita iterativna koda:
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
Izhod
10
Časovna zapletenost: O(len(a)+ log b)
Pomožni prostor: O(1)
Primer: Ko sta tako 'a' kot 'b' zelo velika.
Enak pristop lahko uporabimo tudi, če oboje 'a' in 'b' je bil zelo velik. V tem primeru bi najprej vzeli proti tega z m uporabo našega aModM funkcijo. Nato ga prenesite na zgoraj ApowBmodM rekurzivno ali iterativno funkcijo, da dobimo zahtevani rezultat.
Rekurzivna koda:
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
Izhod
546081867
Časovna zapletenost: O(len(a)+len(b)+log b)
Pomožni prostor: O(logb)
Prostorsko učinkovita iterativna koda:
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
Izhod
546081867
Časovna zapletenost: O(len(a)+len(b)+ log b)
Pomožni prostor: O(1)
Če vam je všeč GeeksforGeeks in bi radi prispevali, lahko tudi napišete članek z uporabo write.geeksforgeeks.org ali pošljite svoj članek na naslov [email protected].
