HackerRank Fundamentals – Russian Peasant Exponentiation

Challenge: Russian Peasant Exponentiation

Subdomeniu: Fundamentals (fundamentals)

Scor cont: 20.0 / 20

Submission status: Accepted

Submission score: 1.0

Submission ID: 464722189

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/russian-peasant-exponentiation/problem

Cerinta

We all know how to calculate $a^b$ using $b$ operations by multiplying $1$ by $a$ a total of $b$ times. The drawback to this method is that $b$ can be large, which makes exponentiation very slow.

There is a well known method called *Russian Peasant Multiplication* that you can read about [here](http://lafstern.org/matt/col3.pdf). 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 \cdot i)^k = c + d \cdot i$ (where $i$ is an imaginary unit) and then print the respective values of $c \text{ mod } m$ and $d \text{ 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).

Output Format

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

Constraints

+ $1 \leq q \leq 10^5$  
+ $0 \leq k \leq 10^{18}$  
+ $2 \leq m \leq 10^9$  
+ $0 \leq a,b \leq m$

Cod sursa

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll mod;
ll mmod(ll n)
{
    return (n-(n/mod)*mod);
}
pair<ll,ll> mul(pair<ll,ll>p1,pair<ll,ll>p2)
{
    ll ans=mmod(p1.first*p2.first-p1.second*p2.second);
    ll ansi=mmod(p1.second*p2.first+p1.first*p2.second);
    return make_pair(ans,ansi);
}
pair<ll,ll> binexp(pair<ll,ll> inp,ll kk)
{
    pair<ll,ll> ans=make_pair(1,0);
    
    while(kk>0)
    {
        if(kk&1)
        {
            ans=mul(ans,inp);
        }
        inp=mul(inp,inp);
        kk/=2;
    }
    
    return ans;
}
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    int t;
    cin>>t;
    while(t--)
    {
        long long a,b,k;
        cin>>a>>b>>k>>mod;
        pair<ll,ll> p;
        p=make_pair(a,b);
        pair<ll,ll> answer=binexp(p,k);
        cout<<(answer.first+mod)%mod<<" "<<(answer.second+mod)%mod<<endl;
        
    }
    return 0;
}