// C++ program to find GCD of two numbers such that // the second number can be very large. #include   using namespace std; typedef long long int ll; // function to find gcd of two integer numbers ll gcd(ll a ll b) {  if (!a)  return b;  return gcd(b % a a); } // Here 'a' is integer and 'b' is string. // The idea is to make the second number (represented // as b) less than and equal to first number by // calculating its mod with first integer number // using basic mathematics ll reduceB(ll a char b[]) {  // Initialize result  ll mod = 0;  // calculating mod of b with a to make  // b like 0 <= b < a  for (int i = 0; i < strlen(b); i++)  mod = (mod * 10 + b[i] - '0') % a;  return mod; // return modulo } // This function returns GCD of 'a' and 'b' // where b can be very large and is represented // as a character array or string ll gcdLarge(ll a char b[]) {  // Reduce 'b' (second number) after modulo with a  ll num = reduceB(a b);  // gcd of two numbers  return gcd(a num); } // Driver program int main() {  // first number which is integer  ll a = 1221;  // second number is represented as string because  // it can not be handled by integer data type  char b[] = '1234567891011121314151617181920212223242526272829';  if (a == 0)  cout << b << endl;  else  cout << gcdLarge(a b) << endl;  return 0; } 

// Java program to find  // GCD of two numbers  // such that the second  // number can be very large. class GFG  {  // This function computes   // the gcd of 2 numbers  private static int gcd(int reduceNum int b)  {  return b == 0 ?   reduceNum : gcd(b reduceNum % b);  }  // Here 'a' is integer and 'b'  // is string. The idea is to make  // the second number (represented   // as b) less than and equal to   // first number by calculating its   // modulus with first integer   // number using basic mathematics  private static int reduceB(int a String b)   {  int result = 0;  for (int i = 0; i < b.length(); i++)   {  result = (result * 10 +  b.charAt(i) - '0') % a;  }  return result;  }  private static int gcdLarge(int a String b)   {  // Reduce 'b' i.e the second   // number after modulo with a  int num = reduceB(a b);    // Nowuse the euclid's algorithm   // to find the gcd of the 2 numbers  return gcd(num a);  }  // Driver code  public static void main(String[] args)   {  // First Number which  // is the integer  int a = 1221;    // Second Number is represented   // as a string because it cannot   // be represented as an integer  // data type  String b = '19837658191095787329';  if (a == 0)  System.out.println(b);  else  System.out.println(gcdLarge(a b));  } // This code is contributed // by Tanishq Saluja. } 

# Python3 program to find GCD of  # two numbers such that the second # number can be very large. # Function to find gcd # of two integer numbers def gcd(a b) : if (a == 0) : return b return gcd(b % a a) # Here 'a' is integer and 'b' is string. # The idea is to make the second number # (represented as b) less than and equal # to first number by calculating its mod # with first integer number using basic # mathematics def reduceB(a b) : # Initialize result mod = 0 # Calculating mod of b with a  # to make b like 0 <= b < a for i in range(0 len(b)) : mod = (mod * 10 + ord(b[i])) % a return mod # return modulo # This function returns GCD of # 'a' and 'b' where b can be # very large and is represented # as a character array or string def gcdLarge(a b) : # Reduce 'b' (second number) # after modulo with a num = reduceB(a b) # gcd of two numbers return gcd(a num) # Driver program # First number which is integer a = 1221 # Second number is represented # as string because it can not # be handled by integer data type b = '1234567891011121314151617181920212223242526272829' if a == 0: print(b) else: print(gcdLarge(a b)) # This code is contributed by Nikita Tiwari. 

// C# program to find GCD of  // two numbers such that the // second number can be very large. using System; class GFG { // function to find gcd // of two integer numbers public long gcd(long a long b) {  if (a == 0)  return b;  return gcd(b % a a); } // Here 'a' is integer and // 'b' is string. The idea  // is to make the second  // number (represented as b) // less than and equal to  // first number by calculating  // its mod with first integer  // number using basic mathematics public long reduceB(long a string b) {  // Initialize result  long mod = 0;  // calculating mod of   // b with a to make  // b like 0 <= b < a  for (int i = 0; i < b.Length; i++)  mod = (mod * 10 +   (b[i] - '0')) % a;  return mod;  } // This function returns GCD  // of 'a' and 'b' where b can // be very large and is  // represented as a character // array or string public long gcdLarge(long a string b) {  // Reduce 'b' (second number)  // after modulo with a  long num = reduceB(a b);  // gcd of two numbers  return gcd(a num); } // Driver Code static void Main() {  // first number   // which is integer  long a = 1221;  // second number is represented   // as string because it can not  // be handled by integer data type  string b = '1234567891011121314151617181920212223242526272829';  GFG p = new GFG();  if (a == 0)  Console.WriteLine(b);  else  Console.WriteLine(p.gcdLarge(a b)); } } // This code is contributed by mits.  

 // PHP program to find GCD of // two numbers such that the  // second number can be very large. // function to find gcd of // two integer numbers function gcd($a $b) { if (!$a) return $b; return gcd($b % $a $a); } // Here 'a' is integer and 'b'  // is string. The idea is to  // make the second number  // (represented as b) less than  // and equal to first number by // calculating its mod with first // integer number using basic mathematics function reduceB($a $b) { // Initialize result $mod = 0; // calculating mod of b with // a to make b like 0 <= b < a for ($i = 0; $i < strlen($b); $i++) $mod = ($mod * 10 + $b[$i] - '0') % $a; // return modulo return $mod; } // This function returns GCD of  // 'a' and 'b' where b can be  // very large and is represented // as a character array or string function gcdLarge($a $b) { // Reduce 'b' (second number) // after modulo with a $num = reduceB($a $b); // gcd of two numbers return gcd($a $num); } // Driver Code // first number which is integer $a = 1221; // second number is represented  // as string because it can not // be handled by integer data type $b = '1234567891011121314151617181920212223242526272829'; if ($a == 0) { echo($b); } else { echo gcdLarge($a $b); } // This code is contributed by nitin mittal.  ?> 

<script> // JavaScript program to find GCD of two numbers such that // the second number can be very large. // function to find gcd of two integer numbers function gcd( a b) {  if (!a)  return b;  return gcd(b%aa); } // Here 'a' is integer and 'b' is string. // The idea is to make the second number (represented // as b) less than and equal to first number by // calculating its mod with first integer number // using basic mathematics function reduceB( a b) {  // Initialize result  let mod = 0;  // calculating mod of b with a to make  // b like 0 <= b < a  for (let i=0; i<b.length-1; i++)  mod = (mod*10 + b[i] - '0')%a;  return mod; // return modulo } // This function returns GCD of 'a' and 'b' // where b can be very large and is represented // as a character array or string function gcdLarge( a b) {  // Reduce 'b' (second number) after modulo with a  let num = reduceB(a b);  // gcd of two numbers  return gcd(a num); } // Driver program  // first number which is integer  let a = 1221;  // second number is represented as string because  // it can not be handled by integer data type  let b = '1234567891011121314151617181920212223242526272829';  if (a == 0)  document.write( b);  else  document.write(gcdLarge(a b)); // This code contributed by aashish1995  </script>