Soluție HackerRank pentru Russian Peasant Exponentiation, subdomeniul Fundamentals, în C++14. Include cerința formatată, exemple, explicația pașilor și…
- Problemă: Russian Peasant Exponentiation
- Domeniu: Fundamentals
- Limbaj: C++14
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
Cerință
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 · i)^k = c + d · 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 ≤ q ≤ 10^5
+ 0 ≤ k ≤ 10^18
+ 2 ≤ m ≤ 10^9
+ 0 ≤ a,b ≤ m
Cod sursă
#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;
}