Algorithm


Problem Name: Mathematics - Russian Peasant Exponentiation

Problem Link: https://www.hackerrank.com/challenges/russian-peasant-exponentiation/problem?isFullScreen=true

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 & Try With Live Editor

#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 & Try With Live Editor

#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 & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Sumar and the Floating Rocks solution in Hackerrank - Hacerrank solution C++, Python
Next
[Solved] Most Distant solution in Hackerrank - Hacerrank solution C, C++, C#, java, js, Python