学步园

原题：http://topic.csdn.net/u/20110623/10/0324c75e-f72a-4894-83e9-f5a00fc88f62.html?85618

描述：有k个正整数 任取其中k-1个数 找到一个他们的最小公倍数数N 求N的最小值

分析：
可以采用以下三种方法：

******************************
1) 方法一：（缺点：需对k个数做质因素分解）

基本想法是先对每个数做质因素分解，然后对k-1个数两两相互统计，找出它们对应质因子的最大个数，最后当所有k-1个数统计结束时，结果就是该质因子个数的最大值，然后将这些质因子相乘（个数>=1,需要重复相乘），找出lcm最小值即可。举个例子：例如有三个数：
x = 12 = 2*2*3;
y = 45 = 3*3*5;
z = 36 = 2*2*3*3

这里k=3,如果取(x，y)这一组共2个数，因为x中的质因子2在y中没有，将它加入lcm的质因子，即lcm=(2*2); x中的质因子3在y中有两个，这时需要在lcm中记录两个3而不是一个3,即lcm=(2*2*3*3); 最后y中的质因子5在x中没有，将它加入lcm的质因子，即lcm=(2*2*3*3*5) = 180。其他两组k-1个数同样处理，最后取最小的lcm就可以得出结果。

对这个例子程序运行结果为：
Input numbers: 12 45 36
(w/o 12), LCM Factors: 2 2 3 2 5 1 lcm: 180
(w/o 45), LCM Factors: 2 2 3 2 lcm: 36
(w/o 36), LCM Factors: 2 2 3 2 5 1 lcm: 180

N: 36

该解法参见下面程序中的solve()函数。

******************************
2）方法二：（优点：无需对k个数做质因素分解；缺点：需k-1个数 --- 共有k组 --- 单独计算）

由于lcm(a,b,c) = lcm(lcm(a,b),c)；而且lcm(a,b)=a*b/gcd(a,b)

其中lcm表示最小公倍数，gcd表示最大公约数。

利用欧几里得算法，可以求得gcd(a,b)。

该解法参见下面程序中的solve2()函数。

******************************

3）方法三：（第二种方法的变体，原理是利用被剔除的元素x做文章）

由于要求k各元素中的k-1个数，考虑能否减少一些计算，首先计算全部元素的最小公倍数lcm(0,1,....k)，然后考虑如何计算下式中的lcm(0,1,...k-1)：

lcm(lcm(0,1,...k-1)，x) = lcm(0,1,....k)

这样，问题转化为在lcm(0,1,....k)和x（这里x为要剔除的某个元素，共有k个这样的元素）已知的情况下，如何求上式中的lcm(0,1,...k-1)?

考虑下图一个实际例子,  假设lcm(0,1,...k)的值为变量lcm，即第一个式子，显然lcm一定能被第二式的x整除(因为lcm是k个数的最小公倍数)。这样x总可以表示成（2）：这里(6)式表示lcm中因子2和5的最大指数来自x；lcm中另外两个因子3和7的最大指数来一定来自lcm(0,1,...k-1)，换句话说，lcm(0,1,...k-1)里面一定有一个因子为(4)式(记作变量contriFactors),最后lcm(0,1,...k-1)可以写成（7）式的形式，即lcm(0,1,...k-1)中因子2的最高指数不超过3，5的最高指数不超过2。

这样问题分解为两部分：1）如何在已知lcm和x的条件下，得出contriFactors的值；2）如何找出lcm(0,1,...k-1)中2和5的最高指数。

第一个部分可以这样计算：由于有条件式（3），将lcm/x得出第(5)式temp的值，这里a和b都大于0，且a=u-u'和b=v-v'。然后不断通过 gcd(temp，x)可以消除x中的因子3和7，即可得到x的伴随变量y。将lcm/y就是第(7)式中左边部分contriFactors的值。

第二部分等价于k-1个数中剔除因子3和7后（得到的数中只含因子2和5）,求它们的最小公倍数(记作变量lcmSub)就可得到。由于剔除因子3和7后，得到的k-1个新数比原来的数要小一些，计算它们的最小公倍数会相对容易一些。

最后将contriFactors乘上第二部分中的最小公倍数lcmSub就是lcm(0,1,...k-1)的值。

值得补充说明的是，如果y=1（即x中没有对lcm的贡献因子），那么(7)式(=lcm)一定是最大值，所以将y=1的情况剔除。也可以将这个方法只用来判断y的值是否为1,如果不为1，仍然按照第二种方法计算k-1个数的最小公倍数。下面solve3()中就是只利用y做判断。(计算第二部分中的最小公倍数lcmSub的代码已被注释掉)

这个解法的的效率高低取决于如何剔除公共因子(即下面的函数removeCommonFactors())。比较遗憾的是：测试证明，其效率比第二种方法要稍微慢一点，原因可能是y=1的数据不多(即对lcm做出贡献因子的数据总体上占的比例较多，对这些数据而言计算y的值等于是多余的操作)。不过比第一种分解质因子的方法要快很多。

该解法参见下面程序中的solve3()函数。

程序：
import java.lang.reflect.Array;<br /> import java.util.HashMap;<br /> import java.util.LinkedList;<br /> import java.util.Map;<br /> /**<br /> *<br /> * @author ljs<br /> * 2011-06-23<br /> *<br /> */<br /> public class K_LCM {<br /> private static final boolean debug = false;<br /> //factors is returned as factor-count pair,e.g.<br /> //n=2*2*2*2*3*5: returns [2,4,3,1,5,1] (factors are in asc. order)<br /> private static LinkedList<Integer> findFactors(int n){<br /> LinkedList<Integer> factorList = new LinkedList<Integer>();<br /> int p = n;<br /> for(int i=2;i<=p;i++){<br /> int count = 0;<br /> while(n % i == 0){<br /> count++;<br /> n /= i;<br /> }<br /> if(count>0){<br /> factorList.add(i);<br /> factorList.add(count);<br /> }<br /> }<br /> return factorList;<br /> }<br /> private static Map<Integer,LinkedList<Integer>> factorAllNumbers(int[] nums){<br /> Map<Integer,LinkedList<Integer>> factoredNumsMap =new HashMap<Integer,LinkedList<Integer>>();<br /> for(int i=0;i<nums.length;i++){<br /> //no need to calculate the factors for duplicate numbers<br /> if(factoredNumsMap.get(nums[i]) == null){<br /> LinkedList<Integer> currFactors = K_LCM.findFactors(nums[i]);<br /> factoredNumsMap.put(nums[i],currFactors);<br /> }<br /> }<br /> return factoredNumsMap;<br /> }</p> <p> private static LinkedList<Integer> findTwoNumbersLCM(LinkedList<Integer> prev,LinkedList<Integer> next){<br /> int j=next.size()-1; //next list's position</p> <p> LinkedList<Integer> curr = new LinkedList<Integer>(prev);<br /> if(curr.size()==0){ //e.g. 1's factors list is empty<br /> curr.addAll(next);<br /> }</p> <p> for(int i=curr.size()-1;i>=0;i-=2){<br /> int count = curr.get(i);<br /> int factor = curr.get(i-1); </p> <p> while(j>=0){<br /> int jcount = next.get(j);<br /> int jfactor = next.get(j-1);<br /> if(jfactor == factor){<br /> if(jcount>count){<br /> //update the factor's count<br /> curr.set(i, jcount);<br /> }<br /> j-=2;<br /> break;<br /> }else {<br /> if(jfactor > factor){<br /> //insert<br /> int insertAt = i + 1;<br /> if(insertAt<curr.size()){<br /> curr.add(insertAt,jcount);<br /> curr.add(insertAt,jfactor);<br /> }else{<br /> curr.addLast(jfactor);<br /> curr.addLast(jcount);<br /> }<br /> j-=2;<br /> //don't move i;<br /> }else {<br /> //add as a first element<br /> if(i-1==0){<br /> curr.addFirst(jcount);<br /> curr.addFirst(jfactor);<br /> j-=2;<br /> //i has moved to head position<br /> }else{<br /> //don't move j<br /> break;<br /> }<br /> }<br /> }<br /> }<br /> }</p> <p> //insert the least factors at the front<br /> while(j>=0){<br /> int jcount = next.get(j);<br /> int jfactor = next.get(j-1);<br /> curr.addFirst(jcount);<br /> curr.addFirst(jfactor);<br /> j-=2;<br /> }</p> <p> return curr;<br /> }</p> <p> private static long findLCM(LinkedList<Integer>[] factorsList){</p> <p> LinkedList<Integer> currFactors = factorsList[0];<br /> for(int i=1;i<factorsList.length;i++){<br /> LinkedList<Integer> nextFactors = factorsList[i];<br /> currFactors = K_LCM.findTwoNumbersLCM(currFactors, nextFactors);<br /> }</p> <p> if(debug){<br /> System.out.format("LCM Factors: ");<br /> for(int factor:currFactors)<br /> System.out.format(" %d",factor);<br /> }</p> <p> //caculate the lcm value<br /> long lcm = 1;<br /> for(int i=0;i<currFactors.size();i+=2){<br /> int factor = currFactors.get(i);<br /> int count = currFactors.get(i+1);<br /> lcm *= (int)Math.pow(factor, count);<br /> }<br /> if(debug){<br /> System.out.format(" lcm: %d",lcm);<br /> System.out.println();<br /> }<br /> return lcm;<br /> }</p> <p> //find the minimum lcm among k-1 numbers (k=nums.length)<br /> @SuppressWarnings("unchecked")<br /> public static long solve(int[] nums){<br /> if(debug){<br /> System.out.format("Using method 1 - Input numbers: ");<br /> for(int num:nums)<br /> System.out.format("%d,",num);<br /> System.out.println();<br /> }<br /> Map<Integer,LinkedList<Integer>> factoredNumsMap =K_LCM.factorAllNumbers(nums);</p> <p> int k =nums.length;<br /> LinkedList<Integer>[] factorsArr =<br /> (LinkedList<Integer>[])Array.newInstance(LinkedList.class,k-1);</p> <p> long lcmMin = Long.MAX_VALUE;<br /> for(int i=0;i<k;i++){<br /> for(int j=0,m=0;j<k;j++){<br /> if(j!=i){<br /> factorsArr[m++] = factoredNumsMap.get(nums[j]);<br /> }<br /> }<br /> if(debug){<br /> System.out.format("(w/o %d), ",nums[i]);<br /> }<br /> long lcm = K_LCM.findLCM(factorsArr);<br /> if(lcm<lcmMin) lcmMin = lcm;<br /> }<br /> if(debug){<br /> System.out.format("%nN=%d%n",lcmMin);<br /> }<br /> return lcmMin;<br /> }</p> <p> public static long gcd(long m,long n){<br /> m = (m<0)?-m:m;<br /> n = (n<0)?-n:n; </p> <p> while(n!=0){<br /> long remainder = m%n;<br /> m = n;<br /> n = remainder;<br /> }<br /> return m;<br /> } </p> <p> public static long solve2(int[] nums){<br /> if(debug){<br /> System.out.format("Using method 2 - Input numbers: ");<br /> for(int num:nums)<br /> System.out.format("%d,",num);<br /> System.out.println();<br /> }</p> <p> int k = nums.length;<br /> long lcmMin = Long.MAX_VALUE;</p> <p> for(int i=0;i<k;i++){<br /> long lcm = 1;<br /> for(int j=0;j<k;j++){<br /> if(j!=i){<br /> lcm = lcm/gcd(lcm,nums[j])*nums[j];<br /> }<br /> }<br /> if(debug) System.out.format("(w/o %d), LCM=%d%n",nums[i],lcm);<br /> if(lcm<lcmMin) lcmMin = lcm;<br /> }<br /> if(debug){<br /> System.out.format("%nN=%d%n",lcmMin);<br /> }<br /> return lcmMin;<br /> }</p> <p> private static long lcm(int[] nums){<br /> //calculate the lcm of the n numbers<br /> long lcm = 1;<br /> for(int j=0;j<nums.length;j++){<br /> lcm = lcm/gcd(lcm,nums[j])*nums[j];<br /> }<br /> return lcm;<br /> }</p> <p> //e.g. a=2^u*3^v*5^w; b=3^r*5^s*7^t, then return:<br /> //b=7^t<br /> private static long removeCommonFactors(long a,long b){<br /> long temp = a;<br /> long gcd = gcd(temp,b);<br /> while(gcd != 1){<br /> b/=gcd;<br /> temp = gcd;<br /> gcd = gcd(gcd,b);<br /> }<br /> return b;<br /> }<br /> //Another version: based on solve2(); no factoring<br /> public static long solve3(int[] nums){<br /> if(debug){<br /> System.out.format("Using method 3 - Input numbers: ");<br /> for(int num:nums)<br /> System.out.format("%d,",num);<br /> System.out.println();<br /> }</p> <p> int k = nums.length;<br /> long lcmMin = Long.MAX_VALUE;</p> <p> long lcm = lcm(nums);</p> <p> for(int i=0;i<k;i++){<br /> int x = nums[i];<br /> long temp = lcm / x;</p> <p> long y = K_LCM.removeCommonFactors(temp,x);</p> <p> if(y==1)<br /> continue;</p> <p> /*<br /> long contriFactors = lcm/y;</p> <p> int[] newNums = new int[k-1];<br /> for(int j=0,m=0;j<k;j++){<br /> if(j!=i){<br /> newNums[m++] = (int)K_LCM.removeCommonFactors(temp,nums[j]);<br /> }<br /> }<br /> long lcmSub = lcm(newNums);<br /> long m = lcmSub * contriFactors;</p> <p> if(debug) System.out.format("(w/o %d), LCM=%d%n",x,m);<br /> if(m<lcmMin) lcmMin = m;<br /> */<br /> long lcmK_1 = 1;<br /> for(int j=0;j<k;j++){<br /> if(j!=i){<br /> lcmK_1 = lcmK_1/gcd(lcmK_1,nums[j])*nums[j];<br /> }<br /> }<br /> if(debug) System.out.format("(w/o %d), LCM=%d%n",x,lcmK_1);<br /> if(lcmK_1<lcmMin) lcmMin = lcmK_1;<br /> }<br /> if(debug){<br /> System.out.format("%nN=%d%n",lcmMin);<br /> }<br /> return lcmMin;<br /> }<br /> public static int[] generateRandIntegers(){<br /> int totalKeys = 10;<br /> int KEYRANGE = 100;<br /> int i=0;<br /> int[] nums = new int[totalKeys];<br /> while(i<totalKeys){<br /> nums[i++] = (int)(Math.random()*KEYRANGE+1);<br /> }<br /> return nums;<br /> }<br /> public static void main(String[] args) { </p> <p> int[] inputNums = new int[]{2*2*2,2*3*3*3,2*3*5,3*3};<br /> long N= K_LCM.solve3(inputNums);<br /> long N0= K_LCM.solve2(inputNums);<br /> if(N != N0){<br /> System.out.println("Test Failed!");<br /> }</p> <p> System.out.println("***************************************");<br /> inputNums = new int[]{9,10,15};<br /> N= K_LCM.solve3(inputNums);<br /> N0= K_LCM.solve2(inputNums);<br /> if(N != N0){<br /> System.out.println("Test Failed!");<br /> }</p> <p> System.out.println("***************************************");<br /> inputNums = new int[]{80,40,79,7,13,39,32,80,74,4};<br /> N= K_LCM.solve3(inputNums);<br /> N0= K_LCM.solve2(inputNums);<br /> if(N != N0){<br /> System.out.println("Test Failed!");<br /> }</p> <p> System.out.println("***************************************");<br /> int testRandCases = 10000;</p> <p> int[][] cases = new int[testRandCases][];<br /> for(int i=0;i<testRandCases;i++){<br /> int[] nums = generateRandIntegers();<br /> cases[i] = nums;<br /> }</p> <p> for(int i=0;i<testRandCases;i++){<br /> int[] nums = cases[i];<br /> long N1= K_LCM.solve(nums);<br /> long N2= K_LCM.solve2(nums);<br /> long N3= K_LCM.solve3(nums);<br /> if(!(N1 == N2 && N2 == N3)){<br /> System.out.format("Input numbers: ");<br /> for(int num:nums)<br /> System.out.format("%d,",num);<br /> System.out.println();</p> <p> System.out.format(" Test Failed!");<br /> System.out.println();<br /> System.out.println();<br /> }<br /> }</p> <p> System.out.println("***************************************");</p> <p> long start = System.currentTimeMillis();<br /> for(int i=0;i<testRandCases;i++){<br /> int[] nums = cases[i];<br /> N= K_LCM.solve(nums);<br /> }<br /> long end = System.currentTimeMillis();<br /> System.out.format("Using method 1 - time cost: %d%n", end-start);<br /> System.out.println("***************************************");</p> <p> start = System.currentTimeMillis();<br /> for(int i=0;i<testRandCases;i++){<br /> int[] nums = cases[i];<br /> N= K_LCM.solve2(nums);<br /> }<br /> end = System.currentTimeMillis();<br /> System.out.format("Using method 2 - time cost: %d%n", end-start);<br /> System.out.println("***************************************");</p> <p> start = System.currentTimeMillis();<br /> for(int i=0;i<testRandCases;i++){<br /> int[] nums = cases[i];<br /> N= K_LCM.solve3(nums);<br /> }<br /> end = System.currentTimeMillis();<br /> System.out.format("Using method 3 - time cost: %d%n", end-start);</p> <p> System.out.println("----END----");<br /> }<br /> }<br />

测试输出：
***************************************
Using method 1 - time cost: 1913
***************************************
Using method 2 - time cost: 350
***************************************
Using method 3 - time cost: 421
----END----

以下是使用这三种方法的一个实例测试结果(输入数据为9,10和15)：

Using method 1 - Input numbers: 9,10,15,
(w/o 9), LCM Factors:  2 1 3 1 5 1  lcm: 30
(w/o 10), LCM Factors:  3 2 5 1  lcm: 45
(w/o 15), LCM Factors:  2 1 3 2 5 1  lcm: 90
N=30

Using method 2 - Input numbers: 9,10,15,
(w/o 9), LCM=30
(w/o 10), LCM=45
(w/o 15), LCM=90
N=30

Using method 3 - Input numbers: 9,10,15,
(w/o 9), LCM=30
(w/o 10), LCM=45
(w/o 15), LCM=90
N=30