给定两个数字“a”和“b”，使得（0<=a<=10^12和b<=b<10^250）。找出两个给定数字的GCD。 例如：
null
Input: a = 978 b = 89798763754892653453379597352537489494736Output: 6Input: a = 1221 b = 1234567891011121314151617181920212223242526272829Output: 3
解决方案： 在给定的问题中，我们可以看到第一个数字“a”可以由long-long int数据类型处理，但第二个数字“b”不能由任何int数据类型处理。在这里，我们把第二个数字读作一个字符串，我们将通过把它的模与a结合，使它小于等于a。 下面是上述想法的实现。
C++
// C++ program to find GCD of two numbers such that // the second number can be very large. #include<bits/stdc++.h> 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 = 0; // 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
// 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); // Now,use 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
# 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#
// 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
<?php // 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. ?> |
Javascript
<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%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 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> |
输出：
3
本文由 沙申克·米什拉（古卢） .本文由Geeksforgeks团队审阅。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
