題解 | 最小眾倍數(shù)
最小眾倍數(shù)
http://www.fangfengwang8.cn/practice/3e9d7d22b7dd4daab695b795d243315b
import java.util.Scanner; import java.util.Collections; import java.util.List; import java.util.ArrayList; import java.lang.Math; // 注意類名必須為 Main, 不要有任何 package xxx 信息 public class Main { public static int MaxGongYin2(int a,int b){ int x = 1; for(int i=100;i>=1;i--){ if(a%i==0 && b%i==0){ x = i; break; } } return (a*b)/(x); } public static int MaxGongYin3(int a,int b,int c){ int tmp = MaxGongYin2(a,b); return MaxGongYin2(tmp,c); } public static void main(String[] args) { String[] inputS = new Scanner(System.in).nextLine().trim().split(" "); // 注意 hasNext 和 hasNextLine 的區(qū)別 ArrayList<Integer> arr = new ArrayList<>(); for(int i=0;i<5;i++){ int num = Integer.parseInt(inputS[i]); arr.add(num); } Collections.sort(arr); int res = Integer.MAX_VALUE; //1.窮舉 for(int i=0;i<arr.size();i++){ for(int j=i+1;j<arr.size();j++){ for(int k=j+1;k<arr.size();k++){ res = Math.min(res,MaxGongYin3(arr.get(i),arr.get(j),arr.get(k))); } } } //2.找特例 for(int i=2;i<arr.size();i++){ int divideNum = 0; for(int j=0;j<i;j++){ if(arr.get(i)%arr.get(j)==0) { divideNum+=1; } if(divideNum>=2) { res = res = Math.min(res,arr.get(i)); break; } } } System.out.println(res); } }
別看代碼長,核心思路很短
需要知道的數(shù)學知識:兩個數(shù)a和b的最小公倍數(shù) = a*b/a和b的最大公因數(shù)
而三個數(shù)a,b,c的最小公倍數(shù)其實就是:a和b的最小公倍數(shù)tmp先求出來,再求tmp和c的最小公倍數(shù),等于是求2次2個數(shù)的最小公倍數(shù)
所以才有了MaxGongYin2和MaxGongYin3兩個函數(shù),看起來多實際上很少
主函數(shù)Main這邊就是先窮舉,找到三個數(shù)情況下的最小公倍數(shù),然后再去找特例,特例情況就是存在一個數(shù)能夠整除其他2個數(shù)