Modular Exponentiation of Complex Numbers |  ; Function to multiply two complex numbers modulo M ; Multiplication of two complex numbers is ( a + ib ) ( c + id ) = ( ac - bd ) + i ( ad + bc ) ; Return the multiplied value ; Function to calculate the complex modular exponentiation ; Here , res is initialised to ( 1 + i0 ) ; If k is odd ; Multiply ' complex ' with ' res ' ; Make complex as complex * complex ; Make k as k / 2 ; Return the required answer ; Driver code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; pair < int , int > Multiply ( pair < int , int > p , pair < int , int > q , int M ) { int x = ( ( p . first * q . first ) % M - ( p . second * q . second ) % M + M ) % M ; int y = ( ( p . first * q . second ) % M + ( p . second * q . first ) % M ) % M ; return { x , y } ; } pair < int , int > compPow ( pair < int , int > complex , int k , int M ) { pair < int , int > res = { 1 , 0 } ; while ( k > 0 ) { if ( k & 1 ) { res = Multiply ( res , complex , M ) ; } complex = Multiply ( complex , complex , M ) ; k = k >> 1 ; } return res ; } int main ( ) { int A = 7 , B = 3 , k = 10 , M = 97 ; pair < int , int > ans = compPow ( { A , B } , k , M ) ; cout << ans . first << " ▁ + ▁ i " << ans . second ; return 0 ; }