HJ108求最小公倍数我是来帮彬彬解决的！进入精彩部分，看题时间到了！让我们来看看这个困扰彬彬的问题，请继续往下看！题目正整数a和正整数b的最小公倍数是指能被a和b整除的最小正整数值。设计一个算法来找到输入a和b的最小公倍数。数据范围：$1\lea,b\le100000$输入说明：输入两个正整数A和B输出说明：输出A和B的最小公倍数例1输入：57输出：35预知如果熟悉最小公倍数、最大公约数、倍数、除数、可除性、除以、除法的概念，可以直接跳过这部分。最小公倍数：两个整数或多个整数的最小公倍数，公倍数就是公倍数，除0外最小的公倍数称为“最小公倍数”。整数a,b的最小公倍数记为：[a,b]整数a,b,c的最小公倍数记为：[a,b,c]等。另一个概念：GreatestCommonDivisor（最大公约数）GreatestCommonDivisor两个整数或多个整数，公约数为公约数，最大公约数为“最大公约数”。整数a,b的最大公约数记为：(a,b)整数a,b,c的最大公约数记为：(a,b,c)倍数和因数的概念如果数a能被数b整除，则a称为b的“倍数”，b称为a的“约数”。除数和倍数都表示一个整数与另一个整数的关系，不能单独存在。需要注意的是，“倍数”和“倍数”是不同的意思！整除的概念整数a除以整数b，即a÷b，商为整数，余数为0，其中a称为“除数”，b称为“除数”，记为b|a（其中符号|为除数的意思），读作b能被a整除，a能被b整除。b称为除数，a称为b的倍数。下面举几个例子：$12÷4=3$读作12除以（divideby）4，或者4除以（divide）12，可以理解为用4除以12，可以分为3部分。12是被除数，4是除数，3是商。4是12的约数，12是4的倍数。同理，$12÷2=6$读作12除以2。可以理解为2用来拆分12，可以分为6个12是被除数，2是除数，6是商。2是12的约数，12是2的倍数。同理$12÷1=12$读作12除以1，可以理解为用1除12。分成12份12就是被除数,1是除数,12是商1是12的除数,12是1的倍数我们再来看这个例子:$16÷4=4$16是被除数,4是除数,商是44是1616是4的倍数$16÷2=8$2是16的倍数,16是2的倍数$16÷1=16$1是16的倍数,16是1的倍数从上面我们可以发现12和16的公约数是1,2,4，其中最大的公约数是4。所以记住12和16的最大公约数是：(12,16)=4448121624的倍数。..6的倍数是6121824...4和6的倍数是1224...，最小的倍数是12，所以记住4和6的最小公倍数是：[4,6]=12这样的梳理，是不是透明了很多~（没看到的时候没说）解题的思路最小公倍数和最大公约数有这个定理：$(a,b)×[a,b]=a×b$，也就是这些数的最小公倍数×这些数的最大公约数=这些数的乘积所以，我们要求两个数的最小公约数，我们可以先求这两个数的最大公约数，然后求这两个数的最小公约数，用这两个数乘以÷这两个数的最大公约数=最小值求解对于公倍数。即$[a,b]=a×b÷(a,b)$那么问题来了，怎么求最大公约数呢？？方法有短分法、滚相分法、多相减法等。这里先用多相减法。多相约减法多相约减法：又称多相约减法，是一种从《九章算术》中求最大公约数的算法。它最初是为归约而设计的，但它适用于任何需要最大公约数的场合。算法步骤如下：首先判断两个数是否为偶数，如果为偶数，则用2进行归约，直到两个数中有一个不为偶数，然后减去较小的数较大的数，然后结合得到的差值与较小的数进行比较，数减去较大的数。继续此操作，直到所得的减数和差值相等。第一步减去的几个2和第二步中间数的乘积就是最大公约数。那么我们就按照这一步来写求两个数的最大公约数的代码：publicstaticintgetGreatestCommonDivisor(inta,intb){//记录两个数为偶数的次数，intcnt=0;//记录最大公约数intans=1;//判断两个数是否偶数，如果偶数，先用2归约while((a&1)==0&&(b&1)==0){a>>=1;b>>=1;++cnt；}//大数减去小数，然后比较小数的差，大数减去小数。//继续这个操作，直到得到的减数和差值相等。while(a!=b){如果(a>b){a-=b;}else{b-=a;}}//计算最大公约数if(cnt!=0){ans=a*(cnt<<1);}else{ans=a;}返回答案；}代码publicclassMain{publicstaticintgetGreatestCommonDivisor(inta,intb){//记录两个数为偶数时2被丢弃的次数intcnt=0;//记录最大公约数intans=1;//判断两个数是否偶数，偶数则用2归约while((a&1)==0&&(b&1)==0){a>>=1;b>>=1;++cnt；}//较大的数减去较小的数，然后比较差值，较小的数减去。//继续这个操作，直到得到的减数和差值相等。while(a!=b){如果(a>b){a-=b;}else{b-=a;}}//计算最大公约数if(cnt!=0){ans=a*(cnt<<1);}else{ans=a;}返回答案；}publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);while(in.hasNext()){inta=in.nextInt();intb=in.nextInt();intlcm=(a*b)/getGreatestCommonDivisor(a,b);System.out.println(lcm);}}}lastlast本人由于水平有限，难免有错误和不足之处。如果屏幕前的美男美少女发现了什么，请指出！最后，感谢您阅读本文，感谢您认真对待我的努力，希望这篇博客对您有所帮助！你轻轻竖起大拇指，那会为我心中的世界增添一颗璀璨耀眼的星！
