给定三个正整数 N , 十、 , Y .任务是打印n次重复x次形成的数字和n次重复y次形成的数字的最大公约数。 0<=n，x，y<=100000000。 例如：
null
Input : n = 123, x = 2, y = 3.Output : 123Number formed are 123123 and 123123123.Greatest Common Divisor of 123123 and123123123 is 123.Input : n = 4, x = 4, y = 6.Output : 44
这个想法是基于 计算两个数GCD的欧氏算法 . 设f（n，x）是一个函数，它给出一个数n重复x次。所以，我们需要找到GCD（f（n，x），f（n，y））。 设n=123，x=3，y=2。 第一个数字A是f（123，3）=123123，第二个数字B是f（123，2）=123123。我们知道，GCD（A，B）=GCD（A–B，B），利用这个性质，我们可以从第一个A中减去B的任意倍数，比如说，只要B’小于A。 所以，A=123123，B’可以是123000。减去A后，A变成123，B保持不变。 因此，A=A-B’=f（n，x-y）。 所以，GCD（f（n，x），f（n，y））=GCD（f（n，x–y），f（n，y）） 我们可以得出以下结论：，
GCD(f(n, x), f(n, y)) = f(n, GCD(x, y)).
以下是基于此方法的实施：
CPP
// C++ program to print Greatest Common Divisor // of number formed by N repeating x times and // y times. #include<bits/stdc++.h> using namespace std; // Return the Greatest common Divisor of two numbers. int gcd( int a, int b) { if (a == 0) return b; return gcd(b%a, a); } // Prints Greatest Common Divisor of number formed // by n repeating x times and y times. void findgcd( int n, int x, int y) { // Finding GCD of x and y. int g = gcd(x,y); // Print n, g times. for ( int i = 0; i < g; i++) cout << n; } // Driven Program int main() { int n = 123, x = 5, y = 2; findgcd(n, x, y); return 0; } |
JAVA
// Java program to print Greatest Common Divisor // of number formed by N repeating x times and // y times class GFG { // Return the Greatest common Divisor // of two numbers. static int gcd( int a, int b) { if (a == 0 ) return b; return gcd(b % a, a); } // Prints Greatest Common Divisor of // number formed by n repeating x // times and y times. static void findgcd( int n, int x, int y) { // Finding GCD of x and y. int g = gcd(x, y); // Print n, g times. for ( int i = 0 ; i < g; i++) System.out.print(n); } // Driver code public static void main(String[] args) { int n = 123 , x = 5 , y = 2 ; findgcd(n, x, y); } } // This code is contributed by Anant Agarwal. |
Python3
# Python program to print Greatest # Common Divisor of number formed # by N repeating x times and y times # Return the Greatest common Divisor # of two numbers. def gcd(a, b): if (a = = 0 ): return b return gcd(b % a, a) # Prints Greatest Common Divisor of # number formed by n repeating x times # and y times. def findgcd(n, x, y): # Finding GCD of x and y. g = gcd(x, y) # Print n, g times. for i in range (g): print (n) # Driver code n = 123 x = 5 y = 2 findgcd(n, x, y) # This code is contributed by Anant Agarwal. |
C#
// C# program to print Greatest Common // Divisor of number formed by N // repeating x times and y times using System; class GFG { // Return the Greatest common // Divisor of two numbers. static int gcd( int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Prints Greatest Common // Divisor of number formed // by n repeating x times // and y times. static void findgcd( int n, int x, int y) { // Finding GCD of x and y. int g = gcd(x, y); // Print n, g times. for ( int i = 0; i < g; i++) Console.Write(n); } // Driver code public static void Main() { int n = 123, x = 5, y = 2; findgcd(n, x, y); } } // This code is contributed by // nitin mittal. |
PHP
<?php // PHP program to print // Greatest Common Divisor // of number formed by N // repeating x times and y times. // Return the Greatest common // Divisor of two numbers. function gcd( $a , $b ) { if ( $a == 0) return $b ; return gcd( $b % $a , $a ); } // Prints Greatest Common Divisor // of number formed by n repeating // x times and y times. function findgcd( $n , $x , $y ) { // Finding GCD of x and y. $g = gcd( $x , $y ); // Print n, g times. for ( $i = 0; $i < $g ; $i ++) echo ( $n ); } // Driver Code $n = 123; $x = 5; $y = 2; findgcd( $n , $x , $y ); // This code is contributed by Ajit. ?> |
Javascript
<script> // Javascript program to print Greatest Common Divisor // of number formed by N repeating x times and // y times. // Return the Greatest common Divisor of two numbers. function gcd(a, b) { if (a == 0) return b; return gcd(b%a, a); } // Prints Greatest Common Divisor of number formed // by n repeating x times and y times. function findgcd(n, x, y) { // Finding GCD of x and y. let g = gcd(x,y); // Print n, g times. for (let i = 0; i < g; i++) document.write(n); } // Driven Program let n = 123, x = 5, y = 2; findgcd(n, x, y); // This is code is contributed by Mayank Tyagi </script> |
输出：
123
本文由 阿努伊·乔汉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
