# 模幂（模运算中的幂）

2021年5月3日17:04:33 发表评论 666 次浏览

## 本文概述

``````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 result

while (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;
}``````

``````(ab) mod p = ( (a mod p) (b mod p) ) mod p

For example a = 50, b = 100, p = 13
50  mod 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 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)
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``````

## C

``````//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 result

x = x % p;  //Update x if it is more than or
//equal to 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)
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 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>> 1      # y = y/2
x = (x * x) % p

return res

# Driver Code

x = 2 ; y = 5 ; p = 13
print ( "Power is " , power(x, y, p))

# This code is contributed by Nikita Tiwari.``````

## C#

``````//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
?>``````

``Power is 6``