数组拆分算法

northwolves

感觉好难好难。楼上最新进展怎样？

liangbch

目前，已经写了多个版本，均不理想，新版本正在编写中。

litaoye

恩，这题挺有意思的，但也挺复杂的。我也提供一个思路供大家参考吧！

基本上就是用贪心，以1024个数为例，其实只需要计算513-1024就可以了，前面的1-512，都是后面的约数，不会成为限制条件

找到513-1024中公约数最大的作为一对，并计算其最小公倍数m，然后再从剩余的数里找到同m公约数最大的数q，并计算m同q的最小公倍m1，
以此类推，直到mi > 2^32，然后对剩余的数重复上面的办法，直到所有数都分组完毕。

这种办法看起来效率比较低，但其实有些地方，有很大的优化空间，首先，1024个数的约数范围为1-1024/3，约数最大的一对为1023（341*3）和682（341 * 2），其次的一对为340*2和340*3......

找到1023和682后，最小公倍为2046，找出2046小于341的最大约数，然后在剩余的数中找到其倍数，就应当是下一个要找的数。然后重新计算2046和该数的最小公倍（应该不用重新算，直接用2046 * 该数 / 约数 就行），再找出小于341的最大约数（这个计算也可以优化），以此类推......

liangbch

22以内的数可分一组
within 22
  lcm1=(16*27*25*7*11*13*17*19) =3,491,888,400        

42以内的数可分2组
within 42
  lcm1=(16*27*25*7*11*13*17*19) =3,491,888,400
  lcm2= (23*29*31*32*37*41*3)   =3,011,232,864

60以内的数可分3组
within 60
  lcm1 (=16*27*25*7*11*13*17*19)
  lcm2 (=23*29*31*32*37*41*3 ) =3,011,232,864
  lcm3 (=43*47*49*53*59*12)    =3,715,964,196

78以内的数可分4组
within 78
  lcm1= (=16*27*25*7*11*13*17*19)=3,491,888,400
  lcm2= (=23*29*31*32*37*41*3 ) =3,011,232,864
  lcm3= (=43*47*49*53*59*12)    =3,715,964,196
  lcm4= (=61*64*67*71*73)       =1,355,706,944

100以内的数可分5组
within 100
  lcm1= (=16*27*25*7*11*13*17*19)=3,491,888,400
  lcm2= (=23*29*31*81*97*4 ) = 649,836,756
  lcm3= (=37*64*79*83*89*3)  = 4,145,702,592.00
  lcm4= (=41*43*47*49*53*2)  =  430,380,034
  lcm5= (=59*61*67*71*73)    = 1,249,792,339.00

shshsh_0510

这个比较难，通用的肯定计算量巨大，就找个特例看看，比如1024
ifactors(factorial(1024))=[1, [[2, 1023], [3, 508], [5, 253], [7, 168], [11, 101], [13, 84], [17, 63],   [19, 55], [23, 45], [29, 36], [31, 34], [37, 27], [41, 24], [43, 23],   [47, 21], [53, 19], [59, 17], [61, 16], [67, 15], [71, 14], [73, 14],   [79, 12], [83, 12], [89, 11], [97, 10], [101, 10], [103, 9], [107, 9],   [109, 9], [113, 9], [127, 8], [131, 7], [137, 7], [139, 7], [149, 6],   [151, 6], [157, 6], [163, 6], [167, 6], [173, 5], [179, 5], [181, 5],   [191, 5], [193, 5], [197, 5], [199, 5], [211, 4], [223, 4], [227, 4],   [229, 4], [233, 4], [239, 4], [241, 4], [251, 4], [257, 3], [263, 3],   [269, 3], [271, 3], [277, 3], [281, 3], [283, 3], [293, 3], [307, 3],   [311, 3], [313, 3], [317, 3], [331, 3], [337, 3], [347, 2], [349, 2],   [353, 2], [359, 2], [367, 2], [373, 2], [379, 2], [383, 2], [389, 2],   [397, 2], [401, 2], [409, 2], [419, 2], [421, 2], [431, 2], [433, 2],   [439, 2], [443, 2], [449, 2], [457, 2], [461, 2], [463, 2], [467, 2],   [479, 2], [487, 2], [491, 2], [499, 2], [503, 2], [509, 2], [521, 1],   [523, 1], [541, 1], [547, 1], [557, 1], [563, 1], [569, 1], [571, 1],   [577, 1], [587, 1], [593, 1], [599, 1], [601, 1], [607, 1], [613, 1],   [617, 1], [619, 1], [631, 1], [641, 1], [643, 1], [647, 1], [653, 1],   [659, 1], [661, 1], [673, 1], [677, 1], [683, 1], [691, 1], [701, 1],   [709, 1], [719, 1], [727, 1], [733, 1], [739, 1], [743, 1], [751, 1],   [757, 1], [761, 1], [769, 1], [773, 1], [787, 1], [797, 1], [809, 1],   [811, 1], [821, 1], [823, 1], [827, 1], [829, 1], [839, 1], [853, 1],   [857, 1], [859, 1], [863, 1], [877, 1], [881, 1], [883, 1], [887, 1],   [907, 1], [911, 1], [919, 1], [929, 1], [937, 1], [941, 1], [947, 1],   [953, 1], [967, 1], [971, 1], [977, 1], [983, 1], [991, 1], [997, 1],   [1009, 1], [1013, 1], [1019, 1], [1021, 1]]]
接下来就看多贪心了
我们假设我们的方案使所有组都是满位(10位10进制），当然这比较难做到。
于是，因子重数为1，2的那些先不管，重数为3的都是些3位数，如果都在一组，有可能给该组公倍数乘2，但不在一组则为另一组减少3位，所以一定放一组
重数为4，5，6的也要放到一组
重数为7的 可能使该组多乘60，而重数为7的都是3位，也合算
重数为8的 就不好说了

于是我们可用分步的贪心：
先将重数为7以上的石头放好，再放那些沙子去调整

shshsh_0510

上面光“大石头”就上百了，况且还要增加如31*31 ，29*29，31*29 ..等“大石头”，看来1024太大了，还是先找个小一点的

liangbch

回无心人，从我的实际应用来讲，n<65536,可用一个WORD类型表示。

这个问题的实际应用。
   为方便起见，我做一些简化。
    有m个分数，m<=n,  通常m很接近于n. 这些分数全部真分数（分子小于分母），且分母互不相同且小于n，求这些分数的和并精确到R位。 R通常大于100而小于65535。
    如果按照通常的做法，复杂度为 m*r, 如果将这些分数分成几组，每一组的各个分数先通分并相加，再做除法则可以提高速度。

当n较大时，实现一个优化的算法比较困看。详细的算法以后再讲，现在先贴出n<223时的分组做法，这个做法是半手工的，但应该是一个接近最佳答案的做法。

下贴出程序运行结果：


check numbers within 22
LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,

check numbers within 42
LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,
LCM[1]=3011232864, bArray[1]=23,29,31,32,37,41,

check numbers within 62
LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,44,45,48,50,51,52,54,55,56,57,60,
LCM[1]=3011232864, bArray[1]=23,29,31,32,37,41,46,58,
LCM[2]=3715964196, bArray[2]=43,47,49,53,59,

check numbers within 78
LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,44,45,48,50,51,52,54,55,56,57,60,63,65,66,68,70,72,75,76,77,78,
LCM[1]=3011232864, bArray[1]=23,29,31,32,37,41,46,58,62,69,74,
LCM[2]=3715964196, bArray[2]=43,47,49,53,59,
LCM[3]=2711413888, bArray[3]=61,64,67,71,73,

check numbers within 100
LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,44,45,48,50,51,52,54,55,56,57,60,63,65,66,68,70,72,75,76,77,78,80,84,85,88,90,91,95,99,100,
LCM[1]=2249244060, bArray[1]=23,29,31,37,46,49,58,62,69,74,87,92,93,98,
LCM[2]=4215967680, bArray[2]=32,41,43,47,53,64,82,86,94,96,
LCM[3]=2773511766, bArray[3]=59,61,67,71,81,
LCM[4]=4132280413, bArray[4]=73,79,83,89,97,

check numbers within 88
LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,44,45,48,50,51,52,54,55,56,57,60,63,65,66,68,70,72,75,76,77,78,80,84,85,88,
LCM[1]=1945292160, bArray[1]=23,29,31,32,46,49,58,62,64,69,87,
LCM[2]=183951420, bArray[2]=37,41,43,47,74,82,86,
LCM[3]=4140735876, bArray[3]=53,59,61,67,81,
LCM[4]=203909586, bArray[4]=71,73,79,83,

check numbers within 106
LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,44,45,48,50,51,52,54,55,56,57,60,63,65,66,68,70,72,75,76,77,78,80,84,85,88,90,91,95,99,100,102,104,105,
LCM[1]=1945292160, bArray[1]=23,29,31,32,46,49,58,62,64,69,87,92,93,96,98,
LCM[2]=183951420, bArray[2]=37,41,43,47,74,82,86,94,
LCM[3]=4140735876, bArray[3]=53,59,61,67,81,106,
LCM[4]=203909586, bArray[4]=71,73,79,83,
LCM[5]=179618198, bArray[5]=89,97,101,103,

check numbers within 124
LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,44,45,48,50,51,52,54,55,56,57,60,63,65,66,68,70,72,75,76,77,78,80,84,85,88,90,91,95,99,100,102,104,105,108,110,112,114,117,119,120,
LCM[1]=1945292160, bArray[1]=23,29,31,32,46,49,58,62,64,69,87,92,93,96,98,115,116,124,
LCM[2]=183951420, bArray[2]=37,41,43,47,74,82,86,94,111,123,
LCM[3]=4140735876, bArray[3]=53,59,61,67,81,106,118,122,
LCM[4]=203909586, bArray[4]=71,73,79,83,
LCM[5]=179618198, bArray[5]=89,97,101,103,
LCM[6]=318936398, bArray[6]=107,109,113,121,

check numbers within 138
LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,44,45,48,50,51,52,54,55,56,57,60,63,65,66,68,70,72,75,76,77,78,80,84,85,88,90,91,95,99,100,102,104,105,108,110,112,114,117,119,120,126,130,132,133,135,136,
LCM[1]=1945292160, bArray[1]=23,29,31,32,46,49,58,62,64,69,87,92,93,96,98,115,116,124,128,138,
LCM[2]=183951420, bArray[2]=37,41,43,47,74,82,86,94,111,123,129,
LCM[3]=4140735876, bArray[3]=53,59,61,67,81,106,118,122,134,
LCM[4]=203909586, bArray[4]=71,73,79,83,
LCM[5]=179618198, bArray[5]=89,97,101,103,
LCM[6]=318936398, bArray[6]=107,109,113,121,
LCM[7]=284908625, bArray[7]=125,127,131,137,

check numbers within 162
LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,44,45,48,50,51,52,54,55,56,57,60,63,65,66,68,70,72,75,76,77,78,80,84,85,88,90,91,95,99,100,102,104,105,108,110,112,114,117,119,120,126,130,132,133,135,136,140,143,144,150,152,153,154,156,
LCM[1]=1945292160, bArray[1]=23,29,31,32,46,49,58,62,64,69,87,92,93,96,98,115,116,124,128,138,145,147,155,160,161,
LCM[2]=183951420, bArray[2]=37,41,43,47,74,82,86,94,111,123,129,141,148,
LCM[3]=4140735876, bArray[3]=53,59,61,67,81,106,118,122,134,159,162,
LCM[4]=203909586, bArray[4]=71,73,79,83,142,146,158,
LCM[5]=179618198, bArray[5]=89,97,101,103,
LCM[6]=318936398, bArray[6]=107,109,113,121,
LCM[7]=284908625, bArray[7]=125,127,131,137,
LCM[8]=490995677, bArray[8]=139,149,151,157,

check numbers within 178
LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,44,45,48,50,51,52,54,55,56,57,60,63,65,66,68,70,72,75,76,77,78,80,84,85,88,90,91,95,99,100,102,104,105,108,110,112,114,117,119,120,126,130,132,133,135,136,140,143,144,150,152,153,154,156,165,168,170,171,175,176,
LCM[1]=1945292160, bArray[1]=23,29,31,32,46,49,58,62,64,69,87,92,93,96,98,115,116,124,128,138,145,147,155,160,161,174,
LCM[2]=183951420, bArray[2]=37,41,43,47,74,82,86,94,111,123,129,141,148,164,172,
LCM[3]=4140735876, bArray[3]=53,59,61,67,81,106,118,122,134,159,162,177,
LCM[4]=203909586, bArray[4]=71,73,79,83,142,146,158,166,
LCM[5]=179618198, bArray[5]=89,97,101,103,178,
LCM[6]=318936398, bArray[6]=107,109,113,121,
LCM[7]=284908625, bArray[7]=125,127,131,137,
LCM[8]=490995677, bArray[8]=139,149,151,157,
LCM[9]=795860377, bArray[9]=163,167,169,173,

check numbers within 196
LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,44,45,48,50,51,52,54,55,56,57,60,63,65,66,68,70,72,75,76,77,78,80,84,85,88,90,91,95,99,100,102,104,105,108,110,112,114,117,119,120,126,130,132,133,135,136,140,143,144,150,152,153,154,156,165,168,170,171,175,176,180,182,187,189,190,195,
LCM[1]=1945292160, bArray[1]=23,29,31,32,46,49,58,62,64,69,87,92,93,96,98,115,116,124,128,138,145,147,155,160,161,174,184,186,192,196,
LCM[2]=183951420, bArray[2]=37,41,43,47,74,82,86,94,111,123,129,141,148,164,172,185,188,
LCM[3]=4140735876, bArray[3]=53,59,61,67,81,106,118,122,134,159,162,177,183,
LCM[4]=203909586, bArray[4]=71,73,79,83,142,146,158,166,
LCM[5]=179618198, bArray[5]=89,97,101,103,178,194,
LCM[6]=318936398, bArray[6]=107,109,113,121,
LCM[7]=284908625, bArray[7]=125,127,131,137,
LCM[8]=490995677, bArray[8]=139,149,151,157,
LCM[9]=795860377, bArray[9]=163,167,169,173,
LCM[10]=1194324337, bArray[10]=179,181,191,193,

check numbers within 222
LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,44,45,48,50,51,52,54,55,56,57,60,63,65,66,68,70,72,75,76,77,78,80,84,85,88,90,91,95,99,100,102,104,105,108,110,112,114,117,119,120,126,130,132,133,135,136,140,143,144,150,152,153,154,156,165,168,170,171,175,176,180,182,187,189,190,195,198,200,204,208,209,210,216,220,221,
LCM[1]=1945292160, bArray[1]=23,29,31,32,46,49,58,62,64,69,87,92,93,96,98,115,116,124,128,138,145,147,155,160,161,174,184,186,192,196,203,217,
LCM[2]=183951420, bArray[2]=37,41,43,47,74,82,86,94,111,123,129,141,148,164,172,185,188,205,215,222,
LCM[3]=4140735876, bArray[3]=53,59,61,67,81,106,118,122,134,159,162,177,183,201,212,
LCM[4]=203909586, bArray[4]=71,73,79,83,142,146,158,166,213,219,
LCM[5]=179618198, bArray[5]=89,97,101,103,178,194,202,206,
LCM[6]=318936398, bArray[6]=107,109,113,121,214,218,
LCM[7]=284908625, bArray[7]=125,127,131,137,
LCM[8]=490995677, bArray[8]=139,149,151,157,
LCM[9]=795860377, bArray[9]=163,167,169,173,
LCM[10]=1194324337, bArray[10]=179,181,191,193,
LCM[11]=1712269431, bArray[11]=197,199,207,211,

再给出代码：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <memory.h>
   
4. 
   
5. typedef unsigned short WORD;
   
6. typedef unsigned long DWORD;
   
7. 
   
8. /*
   
9. 22以内的数可分一组
   
10.   lcm1=(16*27*25*7*11*13*17*19) =3,491,888,400         
    
11. 
    
12. 42以内的数可分2组
    
13.   lcm1=(16*27*25*7*11*13*17*19) =3,491,888,400
    
14.   lcm2= (23*29*31*32*37*41*3)   =3,011,232,864
    
15. 
    
16. 60以内的数可分3组
    
17.   lcm1 (=16*27*25*7*11*13*17*19) =3,491,888,400
    
18.   lcm2 (=23*29*31*32*37*41*3 )   =3,011,232,864
    
19.   lcm3 (=43*47*49*53*59*12)      =3,715,964,196
    
20. 
    
21. 78以内的数可分4组
    
22.   lcm1= (=16*27*25*7*11*13*17*19)=3,491,888,400
    
23.   lcm2= (=23*29*31*32*37*41*3 )  =3,011,232,864
    
24.   lcm3= (=43*47*49*53*59*12)     =3,715,964,196
    
25.   lcm4= (=61*64*67*71*73*3)      =2,711,413,888
    
26. 
    
27. 
    
28. 100以内的数可分5组
    
29.   lcm1 =16*27*25*7*11*13*17*19 =3,491,888,400
    
30.   lcm2 =23*29*31*37*49*3*4*5 =2,249,244,060
    
31.   lcm3 =41*43*47*53*64*3*5 =4,215,967,680
    
32.   lcm4 =59*61*67*81*71*2 =2,773,511,766
    
33.   lcm5 =73*79*83*89*97 =4,132,280,413
    
34. 
    
35. 226以内的数可分12组  
    
36.   lcm1 =16*27*25*7*11*13*17*19 =3,491,888,400  (up to 22)
    
37.   lcm2 =23*29*31*128*49*3*5     =1,945,292,160  (up to 36)
    
38.   lcm3 =37*41*43*47*4*3*5 =183,951,420    (up to 52)
    
39.   lcm4 =53*59*61*67*81*4 =4140735876     (up to 70)
    
40.   lcm5 =71*73*79*83*3*2 =203,909,586    (up to 88)
    
41.   lcm6 =89*97*101*103*2     =179,618,198 (up to 106)
    
42.   lcm7 =107*109*113*121*2 =318,936,398 (up to 124)
    
43.   lcm8 =125*127*131*137 =284,908,625 (up to 138)
    
44.   lcm9 =139*149*151*157 =490,995,677 (up to 162)
    
45.   lcm10=163*167*169*173 =795,860,377 (up to 178)
    
46.   lcm11=179*181*191*193 =1,194,324,337 (up to 196)
    
47.   lcm12=197*199*207*211 =1712269431  (up to 222)
    
48. */
    
49. 
    
50. void verifySplitArray(WORD n, const DWORD lcmArray[],int len)
    
51. {
    
52. WORD *pBuff=new WORD[n];
    
53. int i,j,c1,c2;
    
54. for (i=1;i<=n;i++)
    
55. pBuff[i-1]=i;
    
56. 
    
57. c1=n;
    
58. for (j=0;j<len;j++)
    
59. {
    
60. printf("\nLCM[%d]=%u,bArray[%d]=",j,lcmArray[j],j);
    
61. for (c2=0,i=0;i<c1;i++)
    
62. {
    
63. if (lcmArray[j] % pBuff[i]==0)
    
64. {
    
65. printf("%hu,",pBuff[i]);
    
66. }
    
67. else
    
68. {
    
69. pBuff[c2++]=pBuff[i];
    
70. }
    
71. }
    
72. c1=c2;
    
73. }
    
74. if (c1>0)
    
75. {
    
76. printf("\nThe following is unsort:\n");
    
77. for (i=0;i<c1;i++)
    
78. {
    
79. printf("%hu,",pBuff[i]);
    
80. }
    
81. }
    
82. delete[] pBuff;
    
83. }
    
84. 
    
85. void verifyAll()
    
86. {
    
87. const DWORD lcmArray22[]={3491888400};
    
88. const DWORD lcmArray42[]={3491888400,3011232864};
    
89. const DWORD lcmArray60[]={3491888400, 3011232864,3715964196};
    
90. const DWORD lcmArray78[]={3491888400, 3011232864, 3715964196, 2711413888};
    
91. const DWORD lcmArray100[]={3491888400,2249244060,4215967680, 2773511766,4132280413};
    
92. const DWORD lcmArray222[]=
    
93. {
    
94. 3491888400,1945292160 ,183951420,4140735876,
    
95. 203909586,179618198,318936398,284908625,
    
96. 490995677,795860377,1194324337,1712269431
    
97. };
    
98. 
    
99. printf("\n\ncheck numbers within %d\n",22);
    
100. verifySplitArray(22,lcmArray22,sizeof(lcmArray22)/sizeof(DWORD));
     
101. 
     
102. 
     
103. printf("\n\ncheck numbers within %d\n",42);
     
104. verifySplitArray(42,lcmArray42,sizeof(lcmArray42)/sizeof(DWORD));
     
105. 
     
106. 
     
107. printf("\n\ncheck numbers within %d\n",62);
     
108. verifySplitArray(60,lcmArray60,sizeof(lcmArray60)/sizeof(DWORD));
     
109. 
     
110. 
     
111. printf("\n\ncheck numbers within %d\n",78);
     
112. verifySplitArray(78,lcmArray78,sizeof(lcmArray78)/sizeof(DWORD));
     
113. 
     
114. printf("\n\ncheck numbers within %d\n",100);
     
115. verifySplitArray(100,lcmArray100,sizeof(lcmArray100)/sizeof(DWORD));
     
116. 
     
117. //-------------------------------------------------
     
118. printf("\n\ncheck numbers within %d\n",88);
     
119. verifySplitArray(88,lcmArray222,5);
     
120. 
     
121. printf("\n\ncheck numbers within %d\n",106);
     
122. verifySplitArray(106,lcmArray222,6);
     
123. 
     
124. printf("\n\ncheck numbers within %d\n",124);
     
125. verifySplitArray(124,lcmArray222,7);
     
126. 
     
127. printf("\n\ncheck numbers within %d\n",138);
     
128. verifySplitArray(138,lcmArray222,8);
     
129. 
     
130. printf("\n\ncheck numbers within %d\n",162);
     
131. verifySplitArray(162,lcmArray222,9);
     
132. 
     
133. printf("\n\ncheck numbers within %d\n",178);
     
134. verifySplitArray(178,lcmArray222,10);
     
135. 
     
136. printf("\n\ncheck numbers within %d\n",196);
     
137. verifySplitArray(196,lcmArray222,11);
     
138. 
     
139. printf("\n\ncheck numbers within %d\n",222);
     
140. verifySplitArray(222,lcmArray222,12);
     
141. }
     
142. 
     
143. int main(int argc, char* argv[])
     
144. {
     
145. verifyAll();
     
146. return 0;
     
147. }

复制代码

shshsh_0510

如 27 # medie2005 那样，用2进制 可以分析的更多一些
对于重数为8的因子，如 [127, 8] 分别对应127* 1 - 127*8
乘1，2，3，4显然不用考虑
*5，6，7，8  这4个数，因为127是7位2进制，如果6和8在一组,只给这组增加了2位(乘了3),所以放在一起比较核算
但假如5，6，7这几个数在同一组中而 127*8的这组又不包含3，5，7这几个因子的话， 那么 127*5，127*6，127*7这几个数放在哪组都给该组增加7位 。
但由于上述条件很苛刻，所以倾向于将所有127的倍数都放在一组

liangbch

对于重数为8的因子，如 [127, 8] 分别对应127* 1 - 127*8
乘1，2，3，4显然不用考虑
*5，6，7，8  这4个数，因为127是7位2进制，如果6和8在一组,只给这组增加了2位(乘了3),所以放在一起比较核算

不明白你的意思，127*1 到 127*4 的最小公倍数是 127*3*4
不明白你的意思，127*1 到 127*8 的最小公倍数是 127*8*3*5*7

liangbch

我的分组的基本原则。

第2种方法：
1. 任何一个自然数都可以写成几个质数乘积的乘积。
2. 对n以内所有的数按照质因数的大小排序，首先按照最大质因数排序升序排列，最大质因数相同者按照次大质因数排序，以此类推。
3. 从排序后数组中依次取数，直到这几个数的最小公倍数小于2^32, 将这些数分到一组。
4。重复步骤3，直到数组取空。

例如对16以内的数，排序后将使这个样子
2=2
4=2*2
8=2*2*2
16=2*2*2*2
3=3
6=3*2
12=3*2*2
9=3*3
5=5
10=5*2
15=5*3
7=7
14=7*2
11=11
13=13
14=14
15=15

对于127*1 到 127*8 排序后将是
127
127*2
127*4
127*8
127*3
127*6
127*5
127*7


第3种方法：
1. 任何一个自然数都可以写成几个质数幂的乘积。
2. 对n以内所有的数按照质数幂因子的大小排序，首先按照最大质数幂因子排序升序排列，最大质数幂因子相同者按照次大质数幂因子排序，以此类推。
3. 从排序后数组中依次取数，直到这几个数的最小公倍数小于2^32, 将这些数分到一组。
4。重复步骤3，直到数组取空。

2=2
3=3
6=3*2
4=4
12=4*3
5=5
10=5*2
15=5*3
7=7
14=7*2
8=8
9=9
11=11
13=13
16=16

我倾向于第3个方法。
当然，这只是基本原则，在实际算法实现中，采用了更多的规则，以实现分组最优。