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

本文概述

建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
C ++
C
Java
Python3
C#
的PHP

给定三个数字a, b和c, 我们需要找到(ab) ％ C
现在为什么在求幂后执行"％c", 因为b即使a, b的值相对较小, 它的大小也会非常大, 这是一个问题, 因为我们尝试对问题进行编码的语言的数据类型很可能不会让我们存储这么大的数字。
例子：

Input : a = 2312 b = 3434 c = 6789Output : 6343Input : a = -3 b = 5 c = 89 Output : 24

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。该想法基于以下属性。
属性1：
(m * n)％p具有一个非常有趣的属性：
(m * n)％p =(((m％p)*(n％p))％p
属性2：
如果b是偶数：
(a ^ b)％c =((a ^ b / 2)*(a ^ b / 2))％c？这表明分而治之
如果b是奇数：
(a ^ b)％c =(a *(a ^(b-1))％c
属性3：
如果必须返回绝对值小于y的负数x的mod：
然后(x + y)％y就可以了
注意：
另外, 由于(a ^ b / 2)*(a ^ b / 2)和a *(a ^(b-1)的乘积可能会导致溢出, 因此我们必须注意那些情况
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

// 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.

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

输出如下：