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;

}