呵呵，发现前面说错了。

的确求出最小公倍数那个数，但是那不是结果，那只是过程。

然后把这个数分解成所有不能被分解的数，这些数就是组合那些约束的东西了。

比如10。得到的是6

分解出来是1，2，3这3个。

然后看这3个数能组合成多少个因子，且在10以内，个数又要最多的，数字又要最小的。

这样就把范围划小多了/

循环次数有了大幅度的减少。

出题的人跑哪儿去了？ 怎么没下文了？

不好意思,我也不太懂,想看看大家是怎么想的.

这道题就是求"超级合数"的过程．(9楼的为前５０个超级合数）

应该可以通过质因数来求，而又可以缩小范围：求质因数和筛选素数（应该可以sqrt(n)内）；n>Ｎ／２……这些方面大家应该可以想得比我多

蓝紫色，

请问你是不是原始出题者？ 如果是的，并且自己并没有关于此题的答案， 那么你对时间上的 1s 和空间上256M 的限制的依据是什么？

如果说给出一个解法， 那么我已经给出来了， 但是无法满足你的 一秒 的时间要求。

而现在， 你自己又说自己也没有解决的办法， 那么就不得而知你提出时间和空间限制的依据了。 不知你对此作何解释？

题目是编程比赛题,不是我出的，我只是拿出来看看大家是怎么算的.因为那道题要是按常规算的话,肯定溢出，Ｐ４机速度算的话时间也要很久．

时间并没有1S的限制,不过空间上有256M的限制.

超级合数要满足一些条件的，如肯定大于Ｎ／２，筛除素数（这个又不必Ｎ内求），等

//这是我的方法你可以参考一下.不过不一定完全正确
//我用是结构体,你也用类来实现

typdef stuuct {
int arr;／／公约数的个数

}node［Ｎ］;
／／以下我的实现方法
　scanf("%ld",&n);
void found()
{int m=0;
for(int i=20;i<=n;i++)
{
m=divide();
node[i].arr=m;
m=0;
}
}
int divide(int n)
{ int i;
int x;
for(int i=2;i<=n/2;i++)
if(!(n%i))x++;
return x;
}
void compare( )
{ int max,maxi;
int min,i;
max=node[20].arr;
for(i=21;i<=N;i++)
if(max<node[i].arr)maxi=i;
mini=maxi;
for(i=20;i<N;i++)
if(node[i].arr==node[mini].arr)
if(mini>=i) mini=i;
}
//这样就可以实现了你的结果．你可以到机器上运行一下；
／／最后给我一个答复

我来给你想一想办法．我用的是结构，你也可以用类来实现　
以下是我的想法，不一定正确，你可以参考一下；
#define N 500
typedef strcut {
int arr;//公约数的个数
　　}node[N];
void compare()
{
int m;
int i;
for(i=20;i<N;i++)
{
m=found(i);
node[i].arr=m;
m=0;
}
}
int found(int i)
{
int j,m;
for(j=2;j<=i/2;j++)
if(!(i%j)) m++;
return m;
}
void endcopare()
{ int maxi,mini;
maxi=20;
int i;
for(i=21;i<N;i++)
if(node[i].arr>node[20].arr) maxi=i;
mini=maxi;
for(i=20;i<N;i++)
if(node[i].arr==node[mini].arr)
if(i<mini) mini=i;
printf("%d",mini);
}
这样就可以实现你要的算法了．你可以到机器上运行一下．结果如何．

好贴顶，回去研究下。

回去想了想，觉得思路应当没有大问题了。

首先，这个最大数不会是逐个试出来的。所以 kai 老兄的那个算法很直接，但低效。

这个问题首先是个数学问题。在没有计算机的情况下，遇到这种数学的问题，思路必然不会是穷举。而是寻找这种最大数的特性。通过一个式子计算获得。也许我们可以认为这是一个“纯数学”的思路。

对应的，姑且暂时认定穷举是一种“纯机器”的思路。

但显然，计算机还没有发展到可以忽略计算效率的境界。“纯机器”的思路在速度上时常不能让人满意。
另一方面，很多问题，例如此处的“超级合数”，也鲜有人能够在笔上得到一个计算2^32-1以内“最超级合数”的式子。
所以，人脑和计算机应当彼此公平对待，用“数学”的思维确定大方向，而用“机器”的方法完成烦琐的计算和费神的记忆。实现两者最佳的结合。

这是我在思考此问题时获得的一点体会。相信还能获得多数人的同意。


再说说我对这个问题的思路。

首先是数学上的思路：
将一个数分解质因数。得到类似2^n1 * 3^n2 * 5^n3 * 7^n4 * 11^n5 ……的形式。
则该数的因数个数是(n1+1)(n2+1)(n3+1) …(nk+1)。

那么我们的问题就是
在 A = 2^n1 * 3^n2 * 5^n3 * 7^n4 * 11^n5 ……<= MAX 的条件下
寻求 {n1,n2,n3,…nk}
使 B = (n1+1)(n2+1)(n3+1) …(nk+1) 的值最大。

然后由于

在k值的增加的时候，nk的底数越来越大，增加B所需消耗的增加A的成本也就越大。
而缩小k值的时候，B的因式个数又会减少。也不利于B的增大。

故可以预见。我们所需的{n1,n2,n3…nk}是前两个矛盾妥协的产物。应当是随k的增加，nk单调减的一个数列。

然而准确计算出{n1,n2,n3…nk}是有难度的。所以下面该是机器的活了。

我们需要找到一种尝试路线，不错过让B增大的机会。而竟可能避过不必要的尝试。

我的思路：
先在 n2,n3,…nk = 0 的条件下求出最大n1，也就是算logbase(MAX,2)，
然后在n1>=n2的条件下，以减小n1为代价增大n2。减小量与增大量的比例与底数有关。此处底数为2，3。比例为1：1
同样，在以减小n1,n2为代价增大n3。在n1>n2的情况下优先减小前者。
继续以已获值的n均化后一个n，直到无法保障前面的n不小于后面的n。
在此过程中在A不超过MAX的前提下，保持一个使B最大的{n1,n2,n3…nk}，过程结束后返回。

由于减小量与增大量之间存在的比例限制。在k变大的过程中，该比例会变大，也就是要用更多的2去换取更少的11或97。那么该尝试过程的终点是有相对有限的。而这个比例，为了保证不错过让B增大的机会。我取得是后面底数nq,相对前面底数np的对数再取整。举例的话，用2的指数的减小换11的指数的增加。那么[ logbase(11,2) ] = 3，即需将2的指数减小3来增大11的指数。

而由该过程返回的{n1,n2,n3,…nk}就可算出该超级合数A，也可以得到其所有的约数。


由于尚未将代码写出，难免有漏洞缺失。希望得到大家的指正。

[此贴子已经被作者于2006-11-13 23:20:18编辑过]

我想了下，大概想出个思路，说出来，大家看下。
我接着上一楼的说
我们的问题是
A=2^n1 * 3^n2 * 5^n3 *......* y^k * x^(k+1)<=MAX 且A最小的情况下
求 B=(n1+1)(n2+1)(n3+1) …K*（K+1） 的值最大；
分析：
先令 a1=2^n1 * 3^n2 * 5^n3 *......* y^k * x^(m) b1=(n1+1)(n2+1)(n3+1) …k*m
a2=2^n1 * 3^n2 * 5^n3 *......* y^(k+r1) * x^(m-1) b2=(n1+1)(n2+1)(n3+1) …(k+r1)*(m-1)
a3=2^n1 * 3^n2 * 5^n3 *......* y^(k+r2) * x^(m-2) b3=(n1+1)(n2+1)(n3+1) …(k+r2)*(m-2)
a4=2^n1 * 3^n2 * 5^n3 *......* y^(k+r3) * x^(m-3) b4=(n1+1)(n2+1)(n3+1) …(k+r3)*(m-3)

注意a和b的最后两项。从a1到a4是慢慢变小的，我们用一个最大的质数约束换最多的第二大质数约数，以来使B1尽量大。而b1到b4看最后两项，大家想想，b1到b4是先变大后变小的，或者是直接变小的，不会先变大再变小再变大这样反复。
于是我们便可以用计算机从A的最大项质数约数开始向最小项质数约数扫描，碰到B增大的话就继续上述a1~a4过程，碰到B减小的话就将扫描指针往小的质数约数移。这样只要扫描到有一项B不再增大。便得出了我们要求的A。
先给出个例子：
比如我们求的是100以内的“超级合数”
令A=100=2^2 * 3^0 * 5^2 则约数个数 B=（2+1）*（0+1）*（2+1）=9
现在开始找超级合数
令A1=2^2 * 3^1 * 5^1 B1=(2+1)*(1+1)*(1+1)=12
(现在最大质数约数为5，第二最大约数为3)
(用最大的质数约束换最多的第二大质数约数，以来使B1尽量大，这里3<5<3^2)
令A2=2^2 * 3^2 * 5^0 B2=(2+1)*(2+1)*(0+1)=9<12
(停止这次扫描，将最大约数改为3，第二大约数改为2)
令A3=2^3 * 3^1 * 5^0 B2=(3+1)*(1+1)*(0+1)=8<12
(2<3<2^2)
(停止这次扫描，且整个扫描过程结束)
求超级合数过程结束。我们看到最大的B为B1=12，则A1即为所求。A1=2^2 * 3^1 * 5^1 =60

我的代码也没写出，整个过程我自己看是没什么问题。若有漏洞，希望大家指出
谢谢！

[此贴子已经被作者于2006-10-14 20:11:18编辑过]