给定一个数字n，我们需要找到2的最后两位数 N .
null
例子 :
Input : n = 7Output : 28Input : n = 72Output : 962^72 = 4722366482869645213696
A. 天真的方法 是迭代或使用 战俘 作用计算出2^n的值后，找到最后两位数字并打印出来。
注： 这种方法只适用于2年 N 在一定范围内，如 溢流 发生。
以下是上述方法的实施情况。
C++
// C++ code to find last 2 digits of 2^n #include <bits/stdc++.h> using namespace std; // Find the first digit int LastTwoDigit( long long int num) { // Get the last digit from the number int one = num % 10; // Remove last digit from number num /= 10; // Get the last digit from // the number(last second of num) int tens = num % 10; // Take last digit to ten's position // i.e. last second digit tens *= 10; // Add the value of ones and tens to // make it complete 2 digit number num = tens + one; // return the first digit return num; } // Driver program int main() { int n = 10; long long int num = 1; // pow function used num = pow (2, n); cout << "Last " << 2; cout << " digits of " << 2; cout << "^" << n << " = " ; cout << LastTwoDigit(num) << endl; return 0; } |
JAVA
// Java code to find last 2 digits of 2^n class Geeks { // Find the first digit static long LastTwoDigit( long num) { // Get the last digit from the number long one = num % 10 ; // Remove last digit from number num /= 10 ; // Get the last digit from // the number(last second of num) long tens = num % 10 ; // Take last digit to ten's position // i.e. last second digit tens *= 10 ; // Add the value of ones and tens to // make it complete 2 digit number num = tens + one; // return the first digit return num; } // Driver code public static void main(String args[]) { int n = 10 ; long num = 1 ; // pow function used num = ( long )Math.pow( 2 , n); System.out.println( "Last 2 digits of 2^10 = " +LastTwoDigit(num)); } } // This code is contributed by ankita_saini |
Python3
# Python 3 code to find # last 2 digits of 2^n # Find the first digit def LastTwoDigit(num): # Get the last digit from the number one = num % 10 # Remove last digit from number num / / = 10 # Get the last digit from # the number(last second of num) tens = num % 10 # Take last digit to ten's position # i.e. last second digit tens * = 10 # Add the value of ones and tens to # make it complete 2 digit number num = tens + one # return the first digit return num # Driver Code if __name__ = = "__main__" : n = 10 num = 1 # pow function used num = pow ( 2 , n); print ( "Last " + str ( 2 ) + " digits of " + str ( 2 ) + "^" + str (n) + " = " , end = "") print (LastTwoDigit(num)) # This code is contributed # by ChitraNayal |
C#
// C# code to find last // 2 digits of 2^n using System; class GFG { // Find the first digit static long LastTwoDigit( long num) { // Get the last digit // from the number long one = num % 10; // Remove last digit // from number num /= 10; // Get the last digit // from the number(last // second of num) long tens = num % 10; // Take last digit to // ten's position i.e. // last second digit tens *= 10; // Add the value of ones // and tens to make it // complete 2 digit number num = tens + one; // return the first digit return num; } // Driver code public static void Main(String []args) { int n = 10; long num = 1; // pow function used num = ( long )Math.Pow(2, n); Console.WriteLine( "Last 2 digits of 2^10 = " + LastTwoDigit(num)); } } // This code is contributed // by Ankita_Saini |
PHP
<?php // PHP code to find last // 2 digits of 2^n // Find the first digit function LastTwoDigit( $num ) { // Get the last digit // from the number $one = $num % 10; // Remove last digit // from number $num /= 10; // Get the last digit // from the number(last // second of num) $tens = $num % 10; // Take last digit to // ten's position i.e. // last second digit $tens *= 10; // Add the value of ones // and tens to make it // complete 2 digit number $num = $tens + $one ; // return the first digit return $num ; } // Driver Code $n = 10; $num = 1; // pow function used $num = pow(2, $n ); echo ( "Last " . 2); echo ( " digits of " . 2); echo ( "^" . $n . " = " ); echo ( LastTwoDigit( $num )) ; // This code is contributed // by Shivi_Aggarwal ?> |
Javascript
<script> // Javascript code to find last 2 digits of 2^n // Find the first digit function LastTwoDigit(num) { // Get the last digit from the number let one = num % 10; // Remove last digit from number num = Math.floor(num/10); // Get the last digit from // the number(last second of num) let tens = num % 10; // Take last digit to ten's position // i.e. last second digit tens *= 10; // Add the value of ones and tens to // make it complete 2 digit number num = tens + one; // return the first digit return num; } // Driver program let n = 10; let num = 1; // pow function used num = Math.pow(2, n); document.write( "Last " + 2); document.write( " digits of " + 2); document.write( "^" + n + " = " ); document.write(LastTwoDigit(num) + "<br>" ); // This code is contributed by Mayank Tyagi </script> |
输出：
Last 2 digits of 2^10 = 24
有效方法： 有效的方法是每次乘法后只保留两位数。这个想法与本文中讨论的非常相似 模幂 在讨论求（a^b）%c的一般方法时，这里c是10^2，因为只需要最后两位数字。
以下是上述方法的实施情况。
C++
// C++ code to find last 2 digits of 2^n #include <iostream> using namespace std; /* Iterative Function to calculate (x^y)%p in O(log y) */ int power( long long int x, long long int y, long long int p) { long long int res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res; } // C++ function to calculate // number of digits in x int numberOfDigits( int x) { int i = 0; while (x) { x /= 10; i++; } return i; } // C++ function to print last 2 digits of 2^n void LastTwoDigit( int n) { cout << "Last " << 2; cout << " digits of " << 2; cout << "^" << n << " = " ; // Generating 10^2 int temp = 1; for ( int i = 1; i <= 2; i++) temp *= 10; // Calling modular exponentiation temp = power(2, n, temp); // Printing leftmost zeros. Since (2^n)%2 // can have digits less then 2. In that // case we need to print zeros for ( int i = 0; i < 2 - numberOfDigits(temp); i++) cout << 0; // If temp is not zero then print temp // If temp is zero then already printed if (temp) cout << temp; } // Driver program to test above functions int main() { int n = 72; LastTwoDigit(n); return 0; } |
JAVA
// Java code to find last // 2 digits of 2^n class GFG { /* Iterative Function to calculate (x^y)%p in O(log y) */ static int power( long x, long y, long p) { int res = 1 ; // Initialize result x = x % p; // Update x if it is more // than or equal to p while (y > 0 ) { // If y is odd, multiply // x with result long r = y & 1 ; if (r == 1 ) res = (res * ( int )x) % ( int )p; // y must be even now y = y >> 1 ; // y = y/2 x = (x * x) % p; } return res; } // Java function to calculate // number of digits in x static int numberOfDigits( int x) { int i = 0 ; while (x != 0 ) { x /= 10 ; i++; } return i; } // Java function to print // last 2 digits of 2^n static void LastTwoDigit( int n) { System.out.print( "Last " + 2 + " digits of " + 2 + "^" ); System.out.print(n + " = " ); // Generating 10^2 int temp = 1 ; for ( int i = 1 ; i <= 2 ; i++) temp *= 10 ; // Calling modular exponentiation temp = power( 2 , n, temp); // Printing leftmost zeros. // Since (2^n)%2 can have digits // less then 2. In that case // we need to print zeros for ( int i = 0 ; i < ( 2 - numberOfDigits(temp)); i++) System.out.print( 0 + " " ); // If temp is not zero then // print temp. If temp is zero // then already printed if (temp != 0 ) System.out.println(temp); } // Driver Code public static void main(String[] args) { int n = 72 ; LastTwoDigit(n); } } // This code is contributed // by ChitraNayal |
Python3
# Python 3 code to find # last 2 digits of 2^n # Iterative Function to # calculate (x^y)%p in O(log y) def power(x, y, p): res = 1 # Initialize result x = x % p # Update x if it is more # than or equal to p while (y > 0 ): # If y is odd, multiply # x with result if (y & 1 ): res = (res * x) % p # y must be even now y = y >> 1 # y = y/2 x = (x * x) % p return res # function to calculate # number of digits in x def numberOfDigits(x): i = 0 while (x): x / / = 10 i + = 1 return i # function to print # last 2 digits of 2^n def LastTwoDigit(n): print ( "Last " + str ( 2 ) + " digits of " + str ( 2 ), end = "") print ( "^" + str (n) + " = " , end = "") # Generating 10^2 temp = 1 for i in range ( 1 , 3 ): temp * = 10 # Calling modular exponentiation temp = power( 2 , n, temp) # Printing leftmost zeros. # Since (2^n)%2 can have digits # less then 2. In that case we # need to print zeros for i in range ( 2 - numberOfDigits(temp)): print ( 0 , end = "") # If temp is not zero then print temp # If temp is zero then already printed if temp: print (temp) # Driver Code if __name__ = = "__main__" : n = 72 LastTwoDigit(n) # This code is contributed # by ChitraNayal |
C#
// C# code to find last // 2 digits of 2^n using System; class GFG { /* Iterative Function to calculate (x^y)%p in O(log y) */ static int power( long x, long y, long p) { int res = 1; // Initialize result x = x % p; // Update x if it is more // than or equal to p while (y > 0) { // If y is odd, multiply // x with result long r = y & 1; if (r == 1) res = (res * ( int )x) % ( int )p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res; } // C# function to calculate // number of digits in x static int numberOfDigits( int x) { int i = 0; while (x != 0) { x /= 10; i++; } return i; } // C# function to print // last 2 digits of 2^n static void LastTwoDigit( int n) { Console.Write( "Last " + 2 + " digits of " + 2 + "^" ); Console.Write(n + " = " ); // Generating 10^2 int temp = 1; for ( int i = 1; i <= 2; i++) temp *= 10; // Calling modular exponentiation temp = power(2, n, temp); // Printing leftmost zeros. Since // (2^n)%2 can have digits less // then 2. In that case we need // to print zeros for ( int i = 0; i < ( 2 - numberOfDigits(temp)); i++) Console.Write(0 + " " ); // If temp is not zero then print temp // If temp is zero then already printed if (temp != 0) Console.Write(temp); } // Driver Code public static void Main() { int n = 72; LastTwoDigit(n); } } // This code is contributed // by ChitraNayal |
PHP
<?php // PHP code to find last // 2 digits of 2^n /* Iterative Function to calculate (x^y)%p in O(log y) */ function power( $x , $y , $p ) { $res = 1; // Initialize result $x = $x % $p ; // Update x if it // is more than or // equal to p while ( $y > 0) { // If y is odd, multiply // x with result if ( $y & 1) $res = ( $res * $x ) % $p ; // y must be even now $y = $y >> 1; // y = y/2 $x = ( $x * $x ) % $p ; } return $res ; } // PHP function to calculate // number of digits in x function numberOfDigits( $x ) { $i = 0; while ( $x ) { $x /= 10; $i ++; } return $i ; } // PHP function to print // last 2 digits of 2^n function LastTwoDigit( $n ) { echo ( "Last " . 2); echo ( " digits of " . 2); echo ( "^" . $n . " = " ); // Generating 10^2 $temp = 1; for ( $i = 1; $i <= 2; $i ++) $temp *= 10; // Calling modular // exponentiation $temp = power(2, $n , $temp ); // Printing leftmost zeros. // Since (2^n)%2 can have // digits less then 2. In // that case we need to // print zeros for ( $i = 0; $i < 2 - numberOfDigits( $temp ); $i ++) echo (0); // If temp is not zero then // print temp. If temp is zero // then already printed if ( $temp ) echo ( $temp ); } // Driver Code $n = 72; LastTwoDigit( $n ); // This code is contributed // by Shivi_Aggarwal ?> |
Javascript
<script> // Javascript code to find last // 2 digits of 2^n /* Iterative Function to calculate (x^y)%p in O(log y) */ function power(x, y, p) { let res = 1; // Initialize result x = x % p; // Update x if it is more // than or equal to p while (y > 0) { // If y is odd, multiply // x with result let r = y & 1; if (r == 1) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res; } // JavaScript function to calculate // number of digits in x function numberOfDigits(x) { let i = 0; while (x != 0) { x /= 10; i++; } return i; } // JavaScript function to print // last 2 digits of 2^n function LastTwoDigit(n) { document.write( "Last " + 2 + " digits of " + 2 + "^" ); document.write(n + " = " ); // Generating 10^2 let temp = 1; for (let i = 1; i <= 2; i++) temp *= 10; // Calling modular exponentiation temp = power(2, n, temp); // Printing leftmost zeros. // Since (2^n)%2 can have digits // less then 2. In that case // we need to print zeros for (let i = 0; i < ( 2 - numberOfDigits(temp)); i++) document.write(0 + " " ); // If temp is not zero then // print temp. If temp is zero // then already printed if (temp != 0) document.write(temp); } // driver program let n = 72; LastTwoDigit(n); </script> |
输出：
Last 2 digits of 2^72 = 96
时间复杂性： O（对数n）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
