感觉好难好难。楼上最新进展怎样？
目前，已经写了多个版本，均不理想，新版本正在编写中。
恩，这题挺有意思的，但也挺复杂的。我也提供一个思路供大家参考吧！
基本上就是用贪心，以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的最大约数（这个计算也可以优化），以此类推......
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
这个比较难，通用的肯定计算量巨大，就找个特例看看，比如1024
ifactors(factorial(1024))=, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ]]
接下来就看多贪心了 :)
我们假设我们的方案使所有组都是满位(10位10进制），当然这比较难做到。
于是，因子重数为1，2的那些先不管，重数为3的都是些3位数，如果都在一组，有可能给该组公倍数乘2，但不在一组则为另一组减少3位，所以一定放一组
重数为4，5，6的也要放到一组
重数为7的 可能使该组多乘60，而重数为7的都是3位，也合算
重数为8的 就不好说了
于是我们可用分步的贪心：
先将重数为7以上的石头放好，再放那些沙子去调整
上面光“大石头”就上百了，况且还要增加如31*31 ，29*29，31*29 ..等“大石头”，看来1024太大了，还是先找个小一点的
回无心人，从我的实际应用来讲，n<65536,可用一个WORD类型表示。
这个问题的实际应用。
为方便起见，我做一些简化。
有m个分数，m<=n,通常m很接近于n. 这些分数全部真分数（分子小于分母），且分母互不相同且小于n，求这些分数的和并精确到R位。 R通常大于100而小于65535。
如果按照通常的做法，复杂度为 m*r, 如果将这些分数分成几组，每一组的各个分数先通分并相加，再做除法则可以提高速度。
当n较大时，实现一个优化的算法比较困看。详细的算法以后再讲，现在先贴出n<223时的分组做法，这个做法是半手工的，但应该是一个接近最佳答案的做法。
下贴出程序运行结果：
check numbers within 22
LCM=3491888400, bArray=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=3491888400, bArray=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=3011232864, bArray=23,29,31,32,37,41,
check numbers within 62
LCM=3491888400, bArray=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=3011232864, bArray=23,29,31,32,37,41,46,58,
LCM=3715964196, bArray=43,47,49,53,59,
check numbers within 78
LCM=3491888400, bArray=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=3011232864, bArray=23,29,31,32,37,41,46,58,62,69,74,
LCM=3715964196, bArray=43,47,49,53,59,
LCM=2711413888, bArray=61,64,67,71,73,
check numbers within 100
LCM=3491888400, bArray=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=2249244060, bArray=23,29,31,37,46,49,58,62,69,74,87,92,93,98,
LCM=4215967680, bArray=32,41,43,47,53,64,82,86,94,96,
LCM=2773511766, bArray=59,61,67,71,81,
LCM=4132280413, bArray=73,79,83,89,97,
check numbers within 88
LCM=3491888400, bArray=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=1945292160, bArray=23,29,31,32,46,49,58,62,64,69,87,
LCM=183951420, bArray=37,41,43,47,74,82,86,
LCM=4140735876, bArray=53,59,61,67,81,
LCM=203909586, bArray=71,73,79,83,
check numbers within 106
LCM=3491888400, bArray=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=1945292160, bArray=23,29,31,32,46,49,58,62,64,69,87,92,93,96,98,
LCM=183951420, bArray=37,41,43,47,74,82,86,94,
LCM=4140735876, bArray=53,59,61,67,81,106,
LCM=203909586, bArray=71,73,79,83,
LCM=179618198, bArray=89,97,101,103,
check numbers within 124
LCM=3491888400, bArray=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=1945292160, bArray=23,29,31,32,46,49,58,62,64,69,87,92,93,96,98,115,116,124,
LCM=183951420, bArray=37,41,43,47,74,82,86,94,111,123,
LCM=4140735876, bArray=53,59,61,67,81,106,118,122,
LCM=203909586, bArray=71,73,79,83,
LCM=179618198, bArray=89,97,101,103,
LCM=318936398, bArray=107,109,113,121,
check numbers within 138
LCM=3491888400, bArray=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=1945292160, bArray=23,29,31,32,46,49,58,62,64,69,87,92,93,96,98,115,116,124,128,138,
LCM=183951420, bArray=37,41,43,47,74,82,86,94,111,123,129,
LCM=4140735876, bArray=53,59,61,67,81,106,118,122,134,
LCM=203909586, bArray=71,73,79,83,
LCM=179618198, bArray=89,97,101,103,
LCM=318936398, bArray=107,109,113,121,
LCM=284908625, bArray=125,127,131,137,
check numbers within 162
LCM=3491888400, bArray=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=1945292160, bArray=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=183951420, bArray=37,41,43,47,74,82,86,94,111,123,129,141,148,
LCM=4140735876, bArray=53,59,61,67,81,106,118,122,134,159,162,
LCM=203909586, bArray=71,73,79,83,142,146,158,
LCM=179618198, bArray=89,97,101,103,
LCM=318936398, bArray=107,109,113,121,
LCM=284908625, bArray=125,127,131,137,
LCM=490995677, bArray=139,149,151,157,
check numbers within 178
LCM=3491888400, bArray=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=1945292160, bArray=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=183951420, bArray=37,41,43,47,74,82,86,94,111,123,129,141,148,164,172,
LCM=4140735876, bArray=53,59,61,67,81,106,118,122,134,159,162,177,
LCM=203909586, bArray=71,73,79,83,142,146,158,166,
LCM=179618198, bArray=89,97,101,103,178,
LCM=318936398, bArray=107,109,113,121,
LCM=284908625, bArray=125,127,131,137,
LCM=490995677, bArray=139,149,151,157,
LCM=795860377, bArray=163,167,169,173,
check numbers within 196
LCM=3491888400, bArray=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=1945292160, bArray=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=183951420, bArray=37,41,43,47,74,82,86,94,111,123,129,141,148,164,172,185,188,
LCM=4140735876, bArray=53,59,61,67,81,106,118,122,134,159,162,177,183,
LCM=203909586, bArray=71,73,79,83,142,146,158,166,
LCM=179618198, bArray=89,97,101,103,178,194,
LCM=318936398, bArray=107,109,113,121,
LCM=284908625, bArray=125,127,131,137,
LCM=490995677, bArray=139,149,151,157,
LCM=795860377, bArray=163,167,169,173,
LCM=1194324337, bArray=179,181,191,193,
check numbers within 222
LCM=3491888400, bArray=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=1945292160, bArray=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=183951420, bArray=37,41,43,47,74,82,86,94,111,123,129,141,148,164,172,185,188,205,215,222,
LCM=4140735876, bArray=53,59,61,67,81,106,118,122,134,159,162,177,183,201,212,
LCM=203909586, bArray=71,73,79,83,142,146,158,166,213,219,
LCM=179618198, bArray=89,97,101,103,178,194,202,206,
LCM=318936398, bArray=107,109,113,121,214,218,
LCM=284908625, bArray=125,127,131,137,
LCM=490995677, bArray=139,149,151,157,
LCM=795860377, bArray=163,167,169,173,
LCM=1194324337, bArray=179,181,191,193,
LCM=1712269431, bArray=197,199,207,211,
再给出代码：#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef unsigned short WORD;
typedef unsigned long DWORD;
/*
22以内的数可分一组
lcm1=(16*27*25*7*11*13*17*19) =3,491,888,400
42以内的数可分2组
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组
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
78以内的数可分4组
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*3) =2,711,413,888
100以内的数可分5组
lcm1 =16*27*25*7*11*13*17*19 =3,491,888,400
lcm2 =23*29*31*37*49*3*4*5 =2,249,244,060
lcm3 =41*43*47*53*64*3*5 =4,215,967,680
lcm4 =59*61*67*81*71*2 =2,773,511,766
lcm5 =73*79*83*89*97 =4,132,280,413
226以内的数可分12组
lcm1 =16*27*25*7*11*13*17*19 =3,491,888,400(up to 22)
lcm2 =23*29*31*128*49*3*5 =1,945,292,160(up to 36)
lcm3 =37*41*43*47*4*3*5 =183,951,420 (up to 52)
lcm4 =53*59*61*67*81*4 =4140735876 (up to 70)
lcm5 =71*73*79*83*3*2 =203,909,586 (up to 88)
lcm6 =89*97*101*103*2 =179,618,198 (up to 106)
lcm7 =107*109*113*121*2 =318,936,398 (up to 124)
lcm8 =125*127*131*137 =284,908,625 (up to 138)
lcm9 =139*149*151*157 =490,995,677 (up to 162)
lcm10=163*167*169*173 =795,860,377 (up to 178)
lcm11=179*181*191*193 =1,194,324,337 (up to 196)
lcm12=197*199*207*211 =1712269431(up to 222)
*/
void verifySplitArray(WORD n, const DWORD lcmArray[],int len)
{
WORD *pBuff=new WORD;
int i,j,c1,c2;
for (i=1;i<=n;i++)
pBuff=i;
c1=n;
for (j=0;j<len;j++)
{
printf("\nLCM[%d]=%u,bArray[%d]=",j,lcmArray,j);
for (c2=0,i=0;i<c1;i++)
{
if (lcmArray % pBuff==0)
{
printf("%hu,",pBuff);
}
else
{
pBuff=pBuff;
}
}
c1=c2;
}
if (c1>0)
{
printf("\nThe following is unsort:\n");
for (i=0;i<c1;i++)
{
printf("%hu,",pBuff);
}
}
delete[] pBuff;
}
void verifyAll()
{
const DWORD lcmArray22[]={3491888400};
const DWORD lcmArray42[]={3491888400,3011232864};
const DWORD lcmArray60[]={3491888400, 3011232864,3715964196};
const DWORD lcmArray78[]={3491888400, 3011232864, 3715964196, 2711413888};
const DWORD lcmArray100[]={3491888400,2249244060,4215967680, 2773511766,4132280413};
const DWORD lcmArray222[]=
{
3491888400,1945292160 ,183951420,4140735876,
203909586,179618198,318936398,284908625,
490995677,795860377,1194324337,1712269431
};
printf("\n\ncheck numbers within %d\n",22);
verifySplitArray(22,lcmArray22,sizeof(lcmArray22)/sizeof(DWORD));
printf("\n\ncheck numbers within %d\n",42);
verifySplitArray(42,lcmArray42,sizeof(lcmArray42)/sizeof(DWORD));
printf("\n\ncheck numbers within %d\n",62);
verifySplitArray(60,lcmArray60,sizeof(lcmArray60)/sizeof(DWORD));
printf("\n\ncheck numbers within %d\n",78);
verifySplitArray(78,lcmArray78,sizeof(lcmArray78)/sizeof(DWORD));
printf("\n\ncheck numbers within %d\n",100);
verifySplitArray(100,lcmArray100,sizeof(lcmArray100)/sizeof(DWORD));
//-------------------------------------------------
printf("\n\ncheck numbers within %d\n",88);
verifySplitArray(88,lcmArray222,5);
printf("\n\ncheck numbers within %d\n",106);
verifySplitArray(106,lcmArray222,6);
printf("\n\ncheck numbers within %d\n",124);
verifySplitArray(124,lcmArray222,7);
printf("\n\ncheck numbers within %d\n",138);
verifySplitArray(138,lcmArray222,8);
printf("\n\ncheck numbers within %d\n",162);
verifySplitArray(162,lcmArray222,9);
printf("\n\ncheck numbers within %d\n",178);
verifySplitArray(178,lcmArray222,10);
printf("\n\ncheck numbers within %d\n",196);
verifySplitArray(196,lcmArray222,11);
printf("\n\ncheck numbers within %d\n",222);
verifySplitArray(222,lcmArray222,12);
}
int main(int argc, char* argv[])
{
verifyAll();
return 0;
}
如 27 # medie2005 那样，用2进制 可以分析的更多一些
对于重数为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的倍数都放在一组
对于重数为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
我的分组的基本原则。
第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个方法。
当然，这只是基本原则，在实际算法实现中，采用了更多的规则，以实现分组最优。