考一下大家的算法...

毅歌

这是第38次编程比赛第一题：

在N以内(小于等于N)找出一个数，要求：
1.这个数的约数的个数达到最大，
2.如果有好几个数满足条件1，仅取最小的那个数
说明：
1) 1<N<=2^32-1，每个N的时限是1000ms。内存限制256M,注意使用适当数据类型，以免溢出。
函数原型：
// n: 范围
// result:结果，存放符合条件的那个数
// count:存入存放符合条件的那个数的约数的个数
// arr:存放那个数的所有约数，按照从小到大的顺序
void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[]);
例：
n=100， 则 result=60,
在100以内，60和90的约数个数同为12个，达到这个范围内所有整数中，其约数个数的最大值，但60比90小，所有正确答案为60。60共有12个约数：1,2,3,4,5,6,10.12.15.20.30,60.所以count应该存入12，从arr[0]开始，应该依次写入1,2,3,4,5,6,10.12.15.20.30,60。


写出你们的算法就可以了（当然有程序的也可拿出来），考虑空间以及时间方面的问题，比如说省掉一些不必要的计算

＂Ｍy!ove-、

似乎有点问题，我再看看

新时代

结合例子说一下我的解法： 这个解应该是落在 n/2 与 n 之间， 包括n 本身。

我假定你有了一个方法可以测的某一个数的可约数， 该函数的申明可以是这样的：
void getItsAllDivisor(int n, vector<int> & divisors);

具体以100 这个数为例， 首先我定义一个 类型为 unsigned 变量 number 用来记录这个数 将它初始化为100， 再定义一个 向量容器用来记录该数的所有可约数 vector<unsigned> divisors;

调用函数getItsAllDivisor(number, divisors); 现在你得到了 100 这个数的所有可约的数。

现在用一个for 循环， 从99 一直到 51 在for 循环内部定义一个局部变量 vector<unsigned> temp, 调用函数getItsAllDivisor(i, temp); 然后比较divisors 和temp 的size, 如果temp 的 size 大于等于 divisiors 的 size, 那么使用copy 函数 用temp 覆盖掉 divisors 的内容， 并且将 i 的值付给变量 number, 从而实现对变量 number 的更新。 当这个for 循环结束之后， 我们就得到答案了。 你的函数定义为 void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[]); 所以只要将 变量number 的值付给 result, 将divisors 的 size 付给count, 将divisors 的内容 copy 到数组 arr 就可以了。

℡可可℡

以下是引用kai在2006-9-29 19:47:42的发言：
结合例子说一下我的解法： 这个解应该是落在 n/2 与 n 之间， 包括n 本身。

我假定你有了一个方法可以测的某一个数的可约数， 该函数的申明可以是这样的：
void getItsAllDivisor(int n, vector<int> & divisors);

具体以100 这个数为例， 首先我定义一个 类型为 unsigned 变量 number 用来记录这个数 将它初始化为100， 再定义一个 向量容器用来记录该数的所有可约数 vector<unsigned> divisors;

调用函数getItsAllDivisor(number, divisors); 现在你得到了 100 这个数的所有可约的数。

现在用一个for 循环， 从99 一直到 51 在for 循环内部定义一个局部变量 vector<unsigned> temp, 调用函数getItsAllDivisor(i, temp); 然后比较divisors 和temp 的size, 如果temp 的 size 大于等于 divisiors 的 size, 那么使用copy 函数 用temp 覆盖掉 divisors 的内容， 并且将 i 的值付给变量 number, 从而实现对变量 number 的更新。 当这个for 循环结束之后， 我们就得到答案了。 你的函数定义为 void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[]); 所以只要将 变量number 的值付给 result, 将divisors 的 size 付给count, 将divisors 的内容 copy 到数组 arr 就可以了。
题目要求：1<N<=2^32-1，每个N的时限是1000ms。内存限制256M,注意使用适当数据类型，以免溢出．
２＾３２－１是４０多亿大的数，你的算法能保证１秒得出答案吗？

═━灆涩━═

我也说说我的想法：
2
if大于n;结束 2
判断3%2==0；（如果等于，就把前面的删除，否则不删除）
2*3
if大于n;结束 3
判断4%2==0；（如果等于，就把前面的删除，否则不删除）
3*4；
if大于n;结束 4
判断5%3==0；（如果等于，就把前面的删除，否则不删除）
3*4*5；
if大于n;结束 5
判断6%3==0；（如果等于，就把前面的删除，否则不删除）
4*5*6；
if大于n;结束 6
结束


一直到>=n时，就会知道最基本的有哪些因子。
比如这个题100。
就是到6结束。
所以因子就是1，2，3，4，5，6的各种乘积的集合。


如果是10，那么就是4结束。

成熟之惑

方法倒是有一个， 有点搞笑了， 那就是实现做好一个答案表， 将它存在一个文件里面， 你给出一个数 n , 我就到表里面查一下， 然后给出答案， 这样的话， 1s 完全可以保证。

绝不放弃

以下是引用wfpb在2006-9-29 20:09:50的发言：

我也说说我的想法：
2
if大于n;结束 2
判断3%2==0；（如果等于，就把前面的删除，否则不删除）
2*3
if大于n;结束 3
判断4%2==0；（如果等于，就把前面的删除，否则不删除）
3*4；
if大于n;结束 4
判断5%3==0；（如果等于，就把前面的删除，否则不删除）
3*4*5；
if大于n;结束 5
判断6%3==0；（如果等于，就把前面的删除，否则不删除）
4*5*6；
if大于n;结束 6
结束


一直到>=n时，就会知道最基本的有哪些因子。
比如这个题100。
就是到6结束。
所以因子就是1，2，3，4，5，6的各种乘积的集合。


如果是10，那么就是4结束。





什么意思啊，有点看不懂，是不是求１，２，３，．．．，k的最小公倍数，找到最大的k，使最小公倍数小于n啊？

══════

是啊

斷々弦

以下是引用wfpb在2006-9-29 20:42:06的发言：
是啊
你那个算法是错误的．

前50个总表
序号 合数 分解质因数 约数个数
1 4 2×2 3
2 6 2×3 4
3 12 2×2×3 6
4 24 2×2×2×3 8
5 36 2×2×3×3 9
6 48 2×2×2×2×3 10
7 60 2×2×3×5 12
8 120 2×2×2×3×5 16
9 180 2×2×3×3×5 18
10 240 2×2×2×2×3×5 20
11 360 2×2×2×3×3×5 24
12 720 2×2×2×2×3×3×5 30
13 840 2×2×2×3×5×7 32
14 1260 2×2×3×3×5×7 36
15 1680 2×2×2×2×3×5×7 40
16 2520 2×2×2×3×3×5×7 48
17 5040 2×2×2×2×3×3×5×7 60
18 7560 2×2×2×3×3×3×5×7 64
19 10080 2×2×2×2×2×3×3×5×7 72
20 15120 2×2×2×2×3×3×3×5×7 80
21 20160 2×2×2×2×2×2×3×3×5×7 84
22 25200 2×2×2×2×3×3×5×5×7 90
23 27720 2×2×2×3×3×5×7×11 96
24 45360 2×2×2×2×3×3×3×3×5×7 100
25 50400 2×2×2×2×2×3×3×5×5×7 108
26 55440 2×2×2×2×3×3×5×7×11 120
27 83160 2×2×2×3×3×3×5×7×11 128
28 110880 2×2×2×2×2×3×3×5×7×11 144
29 166320 2×2×2×2×3×3×3×5×7×11 160
30 221760 2×2×2×2×2×2×3×3×5×7×11 168
31 277200 2×2×2×2×3×3×5×5×7×11 180
32 332640 2×2×2×2×2×2×3×3×3×5×7×11 192
33 498960 2×2×2×2×3×3×3×3×5×7×11 200
34 554400 2×2×2×2×2×3×3×5×5×7×11 216
35 665280 2×2×2×2×2×2×3×3×3×5×7×11 224
36 720720 2×2×2×2×3×3×5×7×11×13 240
37 1081080 2×2×2×3×3×3×5×7×11×13 256
38 1441440 2×2×2×2×2×3×3×5×7×11×13 288
39 2162160 2×2×2×2×3×3×3×5×7×11×13 320
40 2882880 2×2×2×2×2×2×3×3×5×7×11×13 336
41 3603600 2×2×2×2×3×3×5×5×7×11×13 360
42 4324320 2×2×2×2×2×3×3×3×5×7×11×13 384
43 6486480 2×2×2×2×3×3×3×3×5×7×11×13 400
44 7207200 2×2×2×2×2×3×3×5×5×7×11×13 432
45 8648640 2×2×2×2×2×2×3×3×3×5×7×11×13 448
46 10810800 2×2×2×2×3×3×3×5×5×7×11×13 480
47 14414400 2×2×2×2×2×2×3×3×5×5×7×11×13 504
48 17297280 2×2×2×2×2×2×2×3×3×3×5×7×11×13 512
49 21621600 2×2×2×2×2×3×3×3×5×5×7×11×13 576
50 32432400 2×2×2×2×3×3×3×3×5×5×7×11×13 600

ˇ风逍遥ˇ

我看错了，对于是否我的想法错了，我不知道。

我不是想求最小公倍数，是答案。

我是说，那些k以下的数字可以构成得到的满足条件的数字的因子。

但答案还不是那个。