## Algorithm

Problem Name: Mathematics - Russian Peasant Exponentiation

In this HackerRank in Mathematics - Russian Peasant Exponentiation solutions,

We all know how to calculate ab using b operations by multiplying 1 by a total of b times. The drawback to this method is that

can be large, which makes exponentiation very slow.

There is a well known method called Russian Peasant Multiplication that you can read about here. Now let's use this to raise some complex numbers to powers!

You're given q queries where each query consists of four integers a,b,k and m. For each query, calculate (a + b * i)= c + d * i (where i is an imaginary unit) and then print the respective values of c mod m and d mod m as two space-separated integers on a new line.

Input Format

The first line contains a single integer, q , denoting the number of queries.
Each of the q subsequent lines describes a query in the form of four space-separated integers: a,b,k and m (respectively).

Constraints

• 1 <= q <= 105
• 0 <= k <= 1018
• 2 <= m <= 109
• 0 <= a,b <= m

Output Format

For each query, print the two space-separated integers denoting the respective values of c mod m and d mod m on a new line.

Sample Input

3
2 0 9 1000
0 1 5 10
8 2 10 1000000000

Sample Output

512 0
0 1
880332800 927506432

Explanation

In the first query, we have a = 2, b = 0, k = 9, m = 1000. We calculate the following:

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ull;
ull MOD;

void mulcomp (ull a, ull b, ull c, ull d, ull &e, ull &f){
e = (((a%MOD)*(c%MOD))%MOD - ((b%MOD)*(d%MOD))%MOD + MOD)%MOD;
f = (((a%MOD)*(d%MOD))%MOD + ((b%MOD)*(c%MOD))%MOD)%MOD;
}

pair  < ull,ull> f(ull real, ull img, ull exp) {
real%=MOD; img%=MOD;
ull ar = 1, ai = 0;
while (exp > 0){
if (exp & 1){
mulcomp(ar, ai, real, img, ar, ai);
}
mulcomp(real, img, real, img, real, img);
exp>>=1;
}
return make_pair(ar, ai);
}

int main(){
int T; cin>>T;
ull a, b, c;
while(T--){
cin>>a>>b>>c>>MOD;
pair < ull,ull> ans = f(a,b,c);
cout << ans.first << " "<<ans.second << "\n";
}
}
Copy The Code &

### #2 Code Example with Java Programming

Code - Java Programming

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

public class Solution {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);
int numberOfTests = scanner.nextInt();
for (int i = 0; i  <  numberOfTests; i++) {
long a = scanner.nextLong();
long b = scanner.nextLong();
long k = scanner.nextLong();
long modulus = scanner.nextLong();

ComplexNumber result = fastComplexExponentian(new ComplexNumber(a % modulus,b % modulus), k, modulus);
System.out.print(printModOfValue(result.getRealPart(), modulus));
System.out.print(" ");
System.out.print(printModOfValue(result.getImaginaryPart(), modulus));
System.out.println("");

}
}

private static ComplexNumber fastComplexExponentian(ComplexNumber base, Long exponent, Long modulus) {

ComplexNumber result = new ComplexNumber(1,0);
while (exponent > 0) {
if (exponent % 2 == 1) {
result = result.multiply(base, modulus);
}
base = base.squareWithMod(modulus);
exponent >>= 1;
}
return result;
}

private static long printModOfValue(long a, long modulus) {
if (a > 0) {
return a % modulus;
} else if(a < 0) {
while(a  <  0) {
a = (((a % modulus) + modulus) % modulus>;
if(a > 0) {
break;
}
}
return a % modulus;
} else {
return 0;
}
}

}

class ComplexNumber {

private final long realPart;
private final long imaginaryPart;

public ComplexNumber(long realPart, long imaginaryPart) {
this.realPart = realPart;
this.imaginaryPart = imaginaryPart;
}

public long getRealPart() {
return realPart;
}

public long getImaginaryPart() {
return imaginaryPart;
}

// (a + ib) ^ 2 = (a^2 - b^2) + i (2 * a * b)
public ComplexNumber squareWithMod(long modulus) {

long a = this.realPart % modulus;
long b = this.imaginaryPart % modulus;

long realPartSquare = ((a * a) % modulus - (b * b) % modulus) % modulus;
long imaginaryPartSquare = ((2 % modulus) * a * b) % modulus;

return new ComplexNumber(realPartSquare, imaginaryPartSquare);
}

// (a + bi) * (c + di) = (ac - bd) + i (bc + ad)
public ComplexNumber multiply(ComplexNumber complexNumber, long modulus) {

long a = this.realPart % modulus;
long b = this.imaginaryPart % modulus;

long c = complexNumber.getRealPart() % modulus;
long d = complexNumber.getImaginaryPart() % modulus;

long newRealPart = (((a * c) % modulus) - ((b * d) % modulus)) % modulus;
long newImaginaryPart = (((a * d) % modulus) + ((b * c) % modulus)) % modulus;

return new ComplexNumber(newRealPart, newImaginaryPart);
}
}
Copy The Code &

### #3 Code Example with Python Programming

Code - Python Programming

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'solve' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts following parameters:
#  1. INTEGER a
#  2. INTEGER b
#  3. LONG_INTEGER k
#  4. INTEGER m
#

def solve(a, b, k, m):
complex_num = complex(a, b) ** k
lst = map(int, [complex_num.real, complex_num.imag])
return list(map(lambda x: x % m, lst))

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

q = int(input().strip())

for q_itr in range(q):
first_multiple_input = input().rstrip().split()

a = int(first_multiple_input[0])

b = int(first_multiple_input[1])

k = int(first_multiple_input[2])

m = int(first_multiple_input[3])

result = solve(a, b, k, m)

fptr.write(' '.join(map(str, result)))
fptr.write('\n')

fptr.close()
Copy The Code &