Equal Squares - Greatest Common Divisor

Problem Discussion:

You have been provided with a paper of dimensions NxM. You have to cut this paper according to the following rules:

1. Paper should be cut along a line parallel to one of the sides of the paper.
2. Paper is cut such that the resultant dimensions are always integer. 

 You need to calculate the minimum number of squares (all of equal size) that can be formed from the given piece of paper.

Input:
The very first line consist of an integer T, total number of testcases. After which T lines follow and each line consist of two space separated integers N and M, dimensions for paper.

Output:
You need to output the required answer, an integer value.

Constraints:

1<=T<=100000
1<=N,M<=10000

Example:
Input:
2
1 1
1 2

Output:
1
2

Algorithm:
To find the minimum number of squares, find the biggest square that can be formed such that all the resulting squares are of equal size.To find the biggest square, calculate the gcd of N and M. The maximum square formed is of the dimension gcd(N,M)xgcd(N,M).
Now to find the minimum number squares, divide the total area of the given piece of paper by the area of the maximum square formed.

Therefore,
Answer=( NxM )/( gcd(N,M) x gcd(N,M) )

Solution:

/*
Date:18th September 2014
Contest:CodeSprint 2k14
Program Code:
Program Description:Cutting paper

submitted by
Arjun Mishra
*/
#include<iostream>
#include<cstdio>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<vector>
#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;
}
int GCD(int a,int b )
{
  if ( a < b )
  return GCD( b, a );
  if ( b == 0 ) return a;
return GCD( b, a % b );
}

int main()
{
int test;
scanf("%d",&test);
while(test--)
{
int N,M,gcd;
N=read();
M=read();
gcd=GCD(N,M);
N=N/gcd;
M=M/gcd;
cout<<N*M<<endl;
}
// getchar();
return 0;

}

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;
}