2 つの数値のうち 1 つが非常に大きくなる場合の 2 つの数値の GCD
(0 <= a <= 10^12 and b <= b < 10^250). Find the GCD of two given numbers.
例:
Input: a = 978 b = 89798763754892653453379597352537489494736 Output: 6 Input: a = 1221 b = 1234567891011121314151617181920212223242526272829 Output: 3
解決 ： 与えられた問題では、最初の数値 'a' は long long int データ型で処理できますが、2 番目の数値 'b' はどの int データ型でも処理できないことがわかります。ここでは 2 番目の数値を文字列として読み取り、それを 'a' で剰余して 'a' 以下にしようとします。
以下は上記のアイデアを実装したものです。
// 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 // 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 # 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 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
時間計算量: O(log (min(ab)))
補助スペース: O(log (min(ab)))
この記事は GeeksforGeeks チームによってレビューされています。
