Algorithm
Problem Name: Mathematics -
https://www.hackerrank.com/challenges/russian-peasant-exponentiation/problem?isFullScreen=true
In this HackerRank in Mathematics -
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)k = 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
Sample Input
3
2 0 9 1000
0 1 5 10
8 2 10 1000000000
Sample Output
512 0
0 1
880332800 927506432
Explanation
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";
}
}
#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);
}
}
#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()