## Problem Link

http://www.spoj.com/problems/GCD2/

## Problem Description

In this problem, we need to find greatest common divisor(GCD) of two numbers.

If there are two numbers, say A and B, then the constraints are :

1. 0<=A<=40000(can be stored in integer)

2. A<=B<=10^250 (can not be stored in integer)

## Concepts Used

Recursion and Maths

## Code

```
#include <bits/stdc++.h>
using namespace std;
//function to find the GCD of two numbers using Eucliedean's algorithm
int gcd(int a, int b) {
if(b==0) {
return a;
}
else {
return gcd(b,a%b);
}
}
int main()
{
int t, i;
int a, b;
char num[300];
scanf("%d",&t);
while(t--) {
scanf("%d%s",&a,num); //two inputs, a number and a character array
if(a==0) //if number first number is 0, then ans would be the second number
{
printf("%s\n",num);
continue;
}
int len = strlen(num); //computing the length of the character array
b = 0; //initializing b to 0
for(i=0;i<len;i++) { //reading the array character by character
b = (b*10+(num[i]-'0'))%a; //maintaining the remainder i.e b%a (Why?See the explaination below)
}
printf("%d\n",gcd(a,b)); //finding the gcd of the first number and the number formed from the above loop
}
return 0;
}
```

## Explanation

The problem can be solved using the Euclid's algorithm for finding GCD of two numbers.

A can be stored in an integer variable but B can't be stored in integer, so it has to be stored in character array or string.

We already know that,

gcd(b,a) = gcd(a,b%a)

Now, what we basically want to do is bring down the range of B to the integer range.

Here, we perform steps similar to basic arithmetic division for calculating a%b.

For example, in order to find 467%3.

1. We take the first digit 4, and do 4%3, which is equal to 1.

2. Then, I bring down the number 1. So, the new number becomes 16. 16%3 will be 1.

3. Bring down 1. the new number will be 17. Again, 17%3 will be 2.

Hence 467%3 = 2.

So, the logic is to read the number digit by digit and maintain the remainder.

This content has been helpful to you?

Thanks for contributing!