Little Panda Solution || Positive and Negative Powers of a Number Solution || Powers and Modulus Solution ||

Little Panda:

            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¹mod X refers to the modular inverse of A modulo X. Since Lucy is impractical, she says that AmodX=(A¹modX)" for n>0. Now she wants Panda to compute A³modX. 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 ABmodX.

Constraints

1<T≤1000

1≤A≤106

-10^6<B≤10^6

1≤x≤10^6

A and X are comprise to each other.

Sample Input

3

123

342

415

Sample Output

1

1

4

Explanation

Case 1: 12mod 3=1 mod 3=1

Case 2: 34mod 2=81 mod 2=1

Case 3: 4¹mod 5=4

Sample input 

3

322

533

7 14

Sample output

1

2

3

Program:

#include <stdio.h>

typedef long long ll;

ll power_mod(ll a, ll b, ll m) {

    ll res = 1;

    while (b > 0) {

        if (b & 1)

            res = (res * a) % m;

        a = (a * a) % m;

        b >>= 1;

    }

    return res;

}

int main() {

    int T;

    scanf("%d", &T);

    while (T--) {

        ll A, B, X;

        scanf("%lld %lld %lld", &A, &B, &X);

        if (B < 0) {

            A = power_mod(A, X - 2, X);

            B = -B;

        }

        printf("%lld\n", power_mod(A, B, X));

    }

}

Explanation:

            Program that calculates the result of modular exponentiation for multiple test cases.

            The power_mod function takes three arguments: a, b, and m. It returns (a^b) % m using the binary exponentiation algorithm. It calculates the result by repeatedly squaring a and reducing the power b by half until b becomes 0. If the current bit of b is 1, it multiplies res by a and takes the modulo m.

            The main function reads the number of test cases T from the user using scanf. It then loops over the test cases and reads three integers A, B, and X using scanf. It checks if B is negative. If so, it calculates the modular inverse of A modulo X and makes B positive. It then calls the power_mod function with the three inputs and prints the result using printf.

            Overall, this program is used to calculate modular exponentiation for multiple test cases efficiently using the binary exponentiation algorithm.