模幂（模运算中的幂）

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

本文概述

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 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;
}

上述解决方案的问题是, 对于较大的n或x值可能会发生溢出。因此, 通常以大数为模来评估功率。

下面是基本的模块化属性, 用于在模块化算术下有效地计算功率。

(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
?>

输出：