HackerRank Number Theory – Little Panda Power

Challenge: Little Panda Power

Subdomeniu: Number Theory (number-theory)

Scor cont: 30.0 / 30

Submission status: Accepted

Submission score: 1.0

Submission ID: 464738437

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/littlepandapower/problem

Cerinta

**Little Panda** has a thing for powers and modulus and he likes challenges. His friend **Lucy**, however, is impractical and challenges **Panda** to find both positive and negative powers of a number modulo a particular number. We all know that $A^{-1}\bmod X$ refers to the modular inverse of $A$ modulo $X$ (see [Wikipedia](http://en.wikipedia.org/wiki/Modular_multiplicative_inverse)).  

Since **Lucy** is impractical, she says that $A^{-n}\bmod  X = (A^{-1}\bmod  X)^n\bmod X$ for $n \gt 0$.  

Now she wants **Panda** to compute $A^B\bmod X$.   

She also thinks that this problem can be very difficult if the constraints aren't given properly. **Little Panda** is very confused and leaves the problem to the worthy programmers of the world. Help him in finding the solution.

**Input Format**  
The first line contains $T$, the number of test cases.  
Then $T$ lines follow, each line containing $A$, $B$ and $X$.  

**Output Format**  
Output the value of $A^B\bmod  X$.  

**Constraints**  
$1 \le T \le 1000$  
$1 \le A \le 10^6$  
$-10^6 \le B \le 10^6$  
$1 \le X \le 10^6$  
$A$  and $X$ are coprime to each other (see [Wikipedia](http://en.wikipedia.org/wiki/Coprime_integers))  

**Sample Input**  

    3  
    1 2 3  
    3 4 2  
    4 -1 5

**Sample Output**  

    1  
    1  
    4  

**Explanation**  
*Case 1:* $1^2\bmod  3 = 1 \bmod  3 = 1$  
*Case 2:* $3^4\bmod  2 = 81 \bmod  2 = 1$  
*Case 3:* $4^{-1}\bmod  5 = 4$

Cod sursa

#include <vector>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <limits.h>
using namespace std;
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define LL long long
#define modulo 1000000007

LL power(LL base, LL exponent, int mod = modulo)
{
    LL res = 1;
    while ( exponent > 0 ) {
        if ( exponent&1 ) res = (res*base)%mod;
        base = (base*base)%mod;
        exponent >>= 1;
    }
    return res;
}

vector<LL> egcd(int a, int b){
    if(a == 0){
        vector<LL> ans;
        ans.pb(b), ans.pb(0), ans.pb(1);
        return ans;
    }
    vector<LL> ret = egcd(b % a, a);
    vector<LL> ans;
    ans.pb(ret[0]), ans.pb(ret[2] - ((b - b%a)/a) * ret[1]), ans.pb(ret[1]);
    return ans;
}

int main(){
    int T;
    cin >> T;
    while(T--){
        int A, B, X;
        cin >> A >> B >> X;
        if(B < 0){
            LL ret = (X + egcd(A, X)[1]) % X;
            cout << power(ret, -B, X) << endl;
        }else cout << power(A, B, X) << endl;
    }
}