Найдите (a ^ b)% m, где 'b' очень велико

Опубликовано: 3 Января, 2022

Даны три числа a, b и m, где 1 <= a, m <= 10 ^ 6. Учитывая очень большое 'b', содержащее до 10 ^ 6 цифр, а m - простое число, задача состоит в том, чтобы найти (a ^ b)% m.
Примеры:

Input: a = 2, b = 3, m = 17
Output: 8
2 ^ 3 % 17 = 8
Input: a = 3, b = 100000000000000000000000000, m = 1000000007
Output: 835987331

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: согласно маленькой теореме Ферма,

 a ^ (p-1) mod p = 1, когда p простое число.

Отсюда, как и в задаче, M простое, выразите A ^ B mod M следующим образом:

 A ^ B mod M = (A ^ (M-1) * A ^ (M-1) * ....... * A ^ (M-1) * A ^ (x)) mod M

Где x - это B по модулю M-1, а A ^ (M-1) продолжается B / (M-1) раз
Теперь, из Маленькой теоремы Ферма,

A ^ (M-1) mod M = 1.

Следовательно,

 A ^ B по модулю M = (1 * 1 * ....... * 1 * A ^ (x)) по модулю M

Следовательно, модифицируйте B с помощью M-1, чтобы уменьшить число до меньшего, а затем используйте метод power () для вычисления (a ^ b)% m.
Ниже представлена реализация описанного выше подхода:

C ++

 // C++ program to find
 // (a^b)%m for b very large.
 #include <bits/stdc++.h>
 #define ll long long int
 using namespace std;
 // Function to find power
 ll power(ll x, ll y, ll p)
 {
    ll res = 1; // Initialize result 
    // Update x if it is more than or
    // equal to p
    x = x % p;
    while (y > 0) {
      
        // If y is odd, multiply x
        // with the 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()
 {
    ll a = 3;
    // String input as b is very large
    string b = "100000000000000000000000000" ; 
    ll remainderB = 0;
    ll MOD = 1000000007;
    // Reduce the number B to a small number
    // using Fermat Little
    for ( int i = 0; i < b.length(); i++)
        remainderB = (remainderB * 10 +
                       b[i] - '0' ) % (MOD - 1); 
    cout << power(a, remainderB, MOD) << endl;
    return 0;
 }

Джава

 // Java program to find
 // (a^b)%m for b very large.
 import java.io.*;
 class GFG
 {
    
// Function to find power
 static long power( long x,
                  long y, long p)
 {
    long res = 1 ; // Initialize result 
    // Update x if it is more
    // than or equal to p
    x = x % p;
    while (y > 0 )
    {
        // If y is odd, multiply
        // x with the result
        if ((y & 1 ) > 0 )
            res = (res * x) % p;
        // y must be even now
        y = y >> 1 ; // y = y/2
        x = (x * x) % p;
    }
    return res;
 }
 // Driver Code
 public static void main (String[] args)
 {
 long a = 3 ;
 // String input as
 // b is very large
 String b = "100000000000000000000000000" ;
 long remainderB = 0 ;
 long MOD = 1000000007 ;
 // Reduce the number B to a small
 // number using Fermat Little
 for ( int i = 0 ; i < b.length(); i++)
    remainderB = (remainderB * 10 +
                  b.charAt(i) - '0' ) %
                 (MOD - 1 );
 System.out.println(power(a, remainderB, MOD));
 }
 }
 // This code is contributed by anuj_67.

Python3

 # Python3 program to find
 # (a^b)%m for b very large.
 # Function to find power
 def power(x, y, p):
    res = 1 # Initialize result 
    # Update x if it is
    # more than or equal to p
    x = x % p 
    while (y > 0 ):
        
        # If y is odd, multiply
        # x with the 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
 a = 3
 # String input as b
 # is very large
 b = "100000000000000000000000000"
 remainderB = 0
 MOD = 1000000007
 # Reduce the number B
 # to a small number
 # using Fermat Little
 for i in range ( len (b)):
    remainderB = ((remainderB * 10 +
                   ord (b[i]) - 48 ) %
                   (MOD - 1 ))
 print (power(a, remainderB, MOD))
 # This code is contributed by mits

C #

 // C# program to find
 // (a^b)%m for b very large.
 using System;
 class GFG
 {
    
// Function to find power
 static long power( long x,
                  long y, long p)
 {
    // Initialize result
    long res = 1; 
    // Update x if it is more
    // than or equal to p
    x = x % p;
    while (y > 0)
    {
        // If y is odd, multiply
        // x with the result
        if ((y & 1) > 0)
            res = (res * x) % p;
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
 }
 // Driver Code
 public static void Main ()
 {
    long a = 3;
    
    // String input as
    // b is very large
    string b = "100000000000000000000000000" ;
    
    long remainderB = 0;
    long MOD = 1000000007;
    
    // Reduce the number B to
    // a small number using
    // Fermat Little
    for ( int i = 0; i < b.Length; i++)
        remainderB = (remainderB * 10 +
                          b[i] - '0' ) %
                             (MOD - 1);
    
    Console.WriteLine(power(a, remainderB, MOD));
 }
 }
 // This code is contributed by anuj_67.

PHP

 <?php
 // PHP program to find
 // (a^b)%m for b very large.
 // Function to find power
 function power( $x , $y , $p )
 {
    $res = 1; // Initialize result 
    // Update x if it is
    // more than or equal to p
    $x = $x % $p ; 
    while ( $y > 0)
    {
        // If y is odd, multiply
        // x with the 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
 $a = 3;
 // String input as b
 // is very large
 $b = "100000000000000000000000000" ;
 $remainderB = 0;
 $MOD = 1000000007;
 // Reduce the number B
 // to a small number
 // using Fermat Little
 for ( $i = 0; $i < strlen ( $b ); $i ++)
    $remainderB = ( $remainderB * 10 +
                   $b [ $i ] - '0' ) %
                  ( $MOD - 1);
 power( echo $a , $remainderB , $MOD );
 // This code is contributed by mits
 ?>

Выход:

835987331

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Олимпиады по программированию Mathematical

Найдите (a ^ b)% m, где 'b' очень велико

C ++

Джава

Python3

C #

PHP

РЕКОМЕНДУЕМЫЕ СТАТЬИ