Rachelle and Interest - Modulus Properties

Problem Discussion:

Rachelle Green has taken loan of $1 from the Byteland Bank.After each passing day, Rachelle is required to pay A times the amount on the previous day.Rachelle wants to know the amount which she has to pay after Xth day.

Rachelle Green being poor in calculations, has come to you for the help.Since, the answer can be very large, tell her answer modulo 1000000007.

Input:

The first line contains an integer T, the number of testcases.It's followed by T lines.Each testcase will contain two integers, A and X, separated with a space.

Ouptut:

Output T lines, each corresponding to the answer of the testcase.

Constraints:

1<=T<=10
1<=A,B<=10^100000

Example:

Input:

5
3 2
4 5
7 4
34534985349875439875439875349875 93475349759384754395743975349573495
34543987529435983745230948023948 3498573497543987543985743989120393097595572309482304

Output:

9
1024
2401
735851262
985546465

Algorithm:

Here we just have to calculate A^X but the challenge is that we cannot accommodate the values of A and X in integer data type.To solve this, we can make use of following properties:

1.( a ^ x ) % m can be calculated as ( a % m ) ^ ( x % (m-1) ).

2.For large numbers' modulus calculation, we can make use of Horner's Method. 

3.And, can further calculate power in O(log n) time complexity.

Solution:

/*
Program Description:Rachelle and Interest - Modulus Properties

submitted by
Arjun Mishra
*/
#include<iostream>
#include<cstdio>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<vector>
#define MAX 100001
#define MOD 1000000007
//#define getchar_unlocked() getchar()
typedef long long LL;
using namespace std;
inline int read() //faster input for integer
{
 int n = 0;
 register char c = getchar_unlocked();//register is used due to its repeated use
 while (!('0' <= c && c <= '9'))
  {
    c = getchar_unlocked();
  }
  while ('0' <= c && c <= '9')
 {
   n = (n<<3) + (n<<1) +  c - '0';//equivalent to n = n*10 + c - 48;
   c = getchar_unlocked();
 }
 return n;
}
LL Horner(char A[MAX],LL M)
{
 LL i=0,a=0;
 while(A[i])
    {
        a=(a*10+(A[i]-'0'))%M;
     i++;
    }
    return a;
}
LL power(LL a,LL x)
{
 LL res = 1;
 while(x > 0)
 {
  if( x % 2 != 0) 
  {
   res = (res * a) % MOD;
  }
  a = (a * a) % MOD;
  x /= 2;
 }
 return res;
}
int main()
{
 int test;
 scanf("%d",&test);
 while(test--)
 {
  char A[MAX]={},X[MAX]={};
  scanf(" %s",A);
  scanf(" %s",X);
  LL a,x;
  a=Horner(A,MOD);
  x=Horner(X,MOD-1);
  printf("%lld\n",power(a,x));
 }
// getchar();
 return 0;
}