# 算法设计：模幂（递归）介绍和代码实现

2021年3月11日17:58:38 发表评论 393 次浏览

## 本文概述

``````Input : a = 2312 b = 3434 c = 6789
Output : 6343

Input : a = -3 b = 5 c = 89
Output : 24``````

## 推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。

(m * n)％p具有一个非常有趣的属性：

(m * n)％p =(((m％p)*(n％p))％p

(a ^ b)％c =((a ^ b / 2)*(a ^ b / 2))％c？这表明分而治之

(a ^ b)％c =(a *(a ^(b-1))％c

## C ++

``````// Recursive C++ program to compute modular power
#include <bits/stdc++.h>
using namespace std;

int exponentMod( int A, int B, int C)
{
// Base cases
if (A == 0)
return 0;
if (B == 0)
return 1;

// If B is even
long y;
if (B % 2 == 0) {
y = exponentMod(A, B / 2, C);
y = (y * y) % C;
}

// If B is odd
else {
y = A % C;
y = (y * exponentMod(A, B - 1, C) % C) % C;
}

return ( int )((y + C) % C);
}

// Driver code
int main()
{
int A = 2, B = 5, C = 13;
cout << "Power is " << exponentMod(A, B, C);
return 0;
}

// This code is contributed by SHUBHAMSINGH10``````

## C

``````// Recursive C program to compute modular power
#include <stdio.h>

int exponentMod( int A, int B, int C)
{
// Base cases
if (A == 0)
return 0;
if (B == 0)
return 1;

// If B is even
long y;
if (B % 2 == 0) {
y = exponentMod(A, B / 2, C);
y = (y * y) % C;
}

// If B is odd
else {
y = A % C;
y = (y * exponentMod(A, B - 1, C) % C) % C;
}

return ( int )((y + C) % C);
}

// Driver program to test above functions
int main()
{
int A = 2, B = 5, C = 13;
printf ( "Power is %d" , exponentMod(A, B, C));
return 0;
}``````

## Java

``````// Recursive Java program
// to compute modular power
import java.io.*;

class GFG
{
static int exponentMod( int A, int B, int C)
{

// Base cases
if (A == 0 )
return 0 ;
if (B == 0 )
return 1 ;

// If B is even
long y;
if (B % 2 == 0 )
{
y = exponentMod(A, B / 2 , C);
y = (y * y) % C;
}

// If B is odd
else
{
y = A % C;
y = (y * exponentMod(A, B - 1 , C) % C) % C;
}

return ( int )((y + C) % C);
}

// Driver Code
public static void main(String args[])
{
int A = 2 , B = 5 , C = 13 ;
System.out.println( "Power is " +
exponentMod(A, B, C));
}
}

// This code is contributed
// by Swetank Modi.``````

## Python3

``````# Recursive Python program
# to compute modular power
def exponentMod(A, B, C):

# Base Cases
if (A = = 0 ):
return 0
if (B = = 0 ):
return 1

# If B is Even
y = 0
if (B % 2 = = 0 ):
y = exponentMod(A, B / 2 , C)
y = (y * y) % C

# If B is Odd
else :
y = A % C
y = (y * exponentMod(A, B - 1 , C) % C) % C
return ((y + C) % C)

# Driver Code
A = 2
B = 5
C = 13
print ( "Power is" , exponentMod(A, B, C))

# This code is contributed
# by Swetank Modi.``````

## C#

``````// Recursive C# program
// to compute modular power
class GFG
{
static int exponentMod( int A, int B, int C)
{

// Base cases
if (A == 0)
return 0;
if (B == 0)
return 1;

// If B is even
long y;
if (B % 2 == 0)
{
y = exponentMod(A, B / 2, C);
y = (y * y) % C;
}

// If B is odd
else
{
y = A % C;
y = (y * exponentMod(A, B - 1, C) % C) % C;
}

return ( int )((y + C) % C);
}

// Driver Code
public static void Main()
{
int A = 2, B = 5, C = 13;
System.Console.WriteLine( "Power is " +
exponentMod(A, B, C));
}
}

// This code is contributed
// by mits``````

## 的PHP

``````<?php
// Recursive PHP program to
// compute modular power
function exponentMod( \$A , \$B , \$C )
{
// Base cases
if ( \$A == 0)
return 0;
if ( \$B == 0)
return 1;

// If B is even
if ( \$B % 2 == 0)
{
\$y = exponentMod( \$A , \$B / 2, \$C );
\$y = ( \$y * \$y ) % \$C ;
}

// If B is odd
else
{
\$y = \$A % \$C ;
\$y = ( \$y * exponentMod( \$A , \$B - 1, \$C ) % \$C ) % \$C ;
}

return (( \$y + \$C ) % \$C );
}

// Driver Code
\$A = 2;
\$B = 5;
\$C = 13;
echo "Power is " . exponentMod( \$A , \$B , \$C );

// This code is contributed
// by Swetank Modi.
?>``````

``Power is 6``