Find remainder when a number A raised to N factorial is divided by P | C ++ program for above approach ; Function to calculate ( A ^ N ! ) % P in O ( log y ) ; Initialize result ; Update x if it is more than or Equal to p ; In case x is divisible by p ; ; If y is odd , multiply x with result ; y must be even now ; Returning modular power ; Function to calculate resultant remainder ; Initializing ans to store final remainder ; Calculating remainder ; Returning resultant remainder ; Driver Code ; Given Input ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; long long int power ( long long x , long long int y , long long int p ) { long long int res = 1 ; x = x % p ; if ( x == 0 ) return 0 ; while ( y > 0 ) { if ( y & 1 ) res = ( res * x ) % p ; y = y >> 1 ; x = ( x * x ) % p ; } return res ; } long long int remainder ( long long int n , long long int a , long long int p ) { long long int ans = a % p ; for ( long long int i = 1 ; i <= n ; i ++ ) ans = power ( ans , i , p ) ; return ans ; } int main ( ) { long long int A = 2 , N = 1 , P = 2 ; cout << remainder ( N , A , P ) << endl ; }