题目描述
输入两个正整数 m 和 n,求其最大公约数和最小公倍数。
样例
5 7
辗转相除法————解决最大公因数和最小公倍数
最大公因数也就是将a和b中更加大的一个数当成 a = kb + r,这样在除余过后,也还是求r和b的最大公因数,然后不断重复这个过程,以达到r为0的地步。而为什么在代码实现中不用管大小呢,是因为代码中无论谁大谁小,在一次递归过后都会变成前者大,后者小的状态。
最小公倍数也就是a*b/(a和b的最小公因数)
时间复杂度
$O(logn)$
参考文献
无
java 代码
import java.io.*;
import java.util.*;
public class Main{
static Scanner sc;
//最大公约数
public static int gcd(int a,int b){
if(b == 0){
return a;
}else{
return gcd(b , a % b);
}
}
public static void main(String[] args) throws IOException{
sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
System.out.print(gcd(a,b) + " ");
System.out.print(a * b / gcd(a,b));
}
}