模幂（模运算中的幂）

本文概述

C ++
C
Java
Python3
C#
的PHP

给定三个数字x, y和p, 计算(x^y)％p。
例子：

Input:x = 2, y = 3, p = 5 Output: 3 Explanation: 2^3 % 5 = 8 % 5 = 3.Input:x = 2, y = 5, p = 13 Output: 6 Explanation: 2^5 % 13 = 32 % 13 = 6.

我们已经讨论过递归的和反复的电力解决方案。
下面讨论迭代解决方案。

/* Iterative Function to calculate (x^y) in O(log y) */ int power( int x, unsigned int y) { int res = 1; //Initialize resultwhile (y> 0) { //If y is odd, multiply x with result if (y & 1) res = res*x; //y must be even now y = y> > 1; //y = y/2 x = x*x; //Change x to x^2 } return res; }

上述解决方案的问题是, 对于较大的n或x值可能会发生溢出。因此, 通常以大数为模来评估功率。
下面是基本的模块化属性, 用于在模块化算术下有效地计算功率。

(ab) mod p = ( (a mod p) (b mod p) ) mod p For example a = 50, b = 100, p = 13 50mod 13= 11 100 mod 13= 9(50 * 100) mod 13 = ( (50 mod 13) * (100 mod 13) ) mod 13 or (5000) mod 13 = ( 11 * 9 ) mod 13 or 8 = 8

下面是基于上述属性的实现。
C ++

//Iterative C++ program to compute modular power #include < iostream> using namespace std; /* Iterative Function to calculate (x^y)%p in O(log y) */ int power( int x, unsigned int y, int p) { int res = 1; //Initialize result x = x % p; //Update x if it is more than or //equal to pif (x == 0) return 0; //In case x is divisible by 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; } //Driver code int main() { int x = 2; int y = 5; int p = 13; cout < < "Power is " < < power(x, y, p); return 0; } //This code is contributed by shubhamsingh10

//Iterative C program to compute modular power #include < stdio.h> /* Iterative Function to calculate (x^y)%p in O(log y) */ int power( int x, unsigned int y, int p) { int res = 1; //Initialize resultx = x % p; //Update x if it is more than or //equal to pif (x == 0) return 0; //In case x is divisible by 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; }//Driver program to test above functions int main() { int x = 2; int y = 5; int p = 13; printf ( "Power is %u" , power(x, y, p)); return 0; }

Java

//Iterative Java program to //compute modular power import java.io.*; class GFG {/* Iterative Function to calculate (x^y)%p in O(log y) */ static int power( int x, int y, int p) { //Initialize result int res = 1 ; //Update x if it is more //than or equal to p x = x % p; if (x == 0 ) return 0 ; //In case x is divisible by p; while (y> 0 ) { //If y is odd, multiply x //with result if ((y & 1 )== 1 ) res = (res * x) % p; //y must be even now //y = y /2 y = y> > 1 ; x = (x * x) % p; } return res; }//Driver Program to test above functions public static void main(String args[]) { int x = 2 ; int y = 5 ; int p = 13 ; System.out.println( "Power is " + power(x, y, p)); } }//This code is contributed by Nikita Tiwari.

Python3

# Iterative Python3 program # to compute modular power# Iterative Function to calculate # (x^y)%p in O(log y) def power(x, y, p) : res = 1# Initialize result# Update x if it is more # than or equal to p x = x % p if (x = = 0 ) : return 0while (y> 0 ) :# If y is odd, multiply # x with result if ((y & 1 ) = = 1 ) : res = (res * x) % p# y must be even now y = y> > 1# y = y/2 x = (x * x) % preturn res# Driver Codex = 2 ; y = 5 ; p = 13 print ( "Power is " , power(x, y, p))# This code is contributed by Nikita Tiwari.

//Iterative C# program to //compute modular power class GFG {/* Iterative Function to calculate (x^y)%p in O(log y) */ static int power( int x, int y, int p) { //Initialize result int res = 1; //Update x if it is more //than or equal to p x = x % p; if (x == 0) return 0; while (y> 0) { //If y is odd, multiply //x with result if ((y & 1) == 1) res = (res * x) % p; //y must be even now //y = y /2 y = y> > 1; x = (x * x) % p; } return res; }//Driver Code public static void Main() { int x = 2; int y = 5; int p = 13; System.Console.WriteLine( "Power is " + power(x, y, p)); } }//This code is contributed by mits

的PHP

< ?php //Iterative PHP program to //compute modular power//Iterative Function to //calculate (x^y)%p in O(log y) function power( $x , $y , $p ) { //Initialize result $res = 1; //Update x if it is more //than or equal to p $x = $x % $p ; if ( $x == 0) return 0; 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/2 $y = $y> > 1; $x = ( $x * $x ) % $p ; } return $res ; }//Driver Code $x = 2; $y = 5; $p = 13; echo "Power is " , power( $x , $y , $p ); //This code is contributed by aj_36 ?>

输出：