CPP Program Advanced GCD – Number Theory

Varun explained its friend Sanchit the algorithm of Euclides to calculate the GCD of two numbers. Then Sanchit implements the algorithm

int gcd(int a, int b)
{
if (b==0)
return a;
else
return gcd(b,a%b);
}

and challenges to Varun to calculate the gcd of two integers, one is a little integer and other integer has 250 digits.
Your task is to help Varun an efficient code for the challenge of Sanchit.

Input format:

• The first line of the input file contains a number representing the number of lines to follow.
• Each line consists of two number A and B (0 <= A <= 40000 and A <= B < 10^250).

Output format:

Print for each pair (A,B) in the input one integer representing the GCD of A and B.

Constraints:

1 <= n <= 1000

Sample Input:

2
2 6
10 11

2
1

Code:

#include<iostream>
#include<string>
using namespace std;
int gcd(int a, int b)
{
    if(b>a)
    {
        return gcd(b, a);
    }
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int a;
        string b;
        cin >> a >> b;
        if(a==0)
        {
            cout<<b<<endl;
            continue;
        }
        int current_number = 0;
        for (int i = 0; i < b.size(); i++)
        {
            current_number = ((current_number * 10) % a + (b[i] - '0') % a) % a;
        }
        cout << gcd(a, current_number) << endl;
    }
}
Code language: C++ (cpp)