第38次编程比赛第一题的一个超快速算法 这个算法计算速度超快,我只是按设计的算法粗糙的实现了一下,当N=4000000000(四十亿)的时候,计算时间不超过100毫秒, 我没有具体测这个时间,只是一运行,马上就会出结果,无需等待. ////////////////////////////////////////////////////// 原题目 在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。 /////////////////////////////////////////////////////////////////////////// 在描述这个算法之前，我们先来讨论一下一个问题， 怎么一个数M的因子个数呢？ 最容易想到的算法就是拿1~M的所有数都去除M，能整除的就是M的因子，然后再统计出因子的个数，然而这种方法也是最慢的，如果用这种方法去解比赛的那个题目，N比较小是还可以，当N比较大时，估计你我在有生之年都无法看到结果了，呵呵。 这时你也需想到了另一个快一些的方法，就是用互质因子的组合来求因子，过程是这样的 先把M分解质因数，（这个过程不难，也有比较快速的算法） 如：30可分解成2*3*5。那它的因数个数就是2^3个，为什么呢？如下： 2 3 5 变量 x1 x2 x3 可取的值 1或2 1或3 1或5 （也就是Xi的0次方和Xi的1次方) 当x1,x2,x3取不同值时，X1*X2*X3的各个结果都是30的因子。根据组合的理论，因子的个数一共是2*2*2＝8（为什么？呵呵，好好想想）; 这时你可能发现了一个问题 ，就是当M分解质因数后，它的质因子有重复的怎么办呢？ 如M=60，质因子为2*2*3*5，有两个2，这种情况怎么算呢？ 我们只要把2合为一组，情况如下： 2 3 5 变量 x1 x2 x3 可取的值 1或2或4 1或3 1或5 （X1的可取值不只是2^0和2^1了，多了一个2^2。这个也不难理解吧！） 那么60的因子个数为3×2*2＝12了。 总结规律： 把M分解质因数后我们可以得到这样两个序列： Zi ： M的互异的质因子（M=60时 Zi为2,3,5） Yi ： 对就质因子出现的次数（M=60时 Yi为2,1,1） 为了容易理解怎么求M的因数，我们用到了另一个序列 Xi 对Xi每一元素的可取值为Zi^0,Zi^1,Zi^2.....Zi^Yi 也就是可以取Yi+1种不同的值。 让Xi取不同的值，X1×X2*X3........×Xm的结果就构成了M的所有因子， 而因子的总个数也可简单的用 （Y1+1)×（Y2+1)*(Y3+1)......*(Ym+1)来求的. 以上只是介绍了怎么样求M的因子和因子总数,若要解比赛的题目,还需要对(N/2)到N的所有数的因数总数求出来进行比较,才能找出结果.由于N比较大.这个过程也是比较耗时的.(我测了一下.当N=100000(十万)时),要找出结果要用大约20秒,我的程序没有优化,若优化一下,时间也不会太短. 那还有没有更好的算法来解比赛的题目呢? 有! 细心的你可能发现了上面求M的因子的一个很有趣的规律,那就要想求出M的因子的总个数只要用Yi序列和质因数个数就可以了,而不需要其它的,也就是说因子的总个数与M分解的质因数的具体值无关,只与各质因数出现的次数有关.这个发现太重要,它是这个快速算法的核心. 再往下想一步,对于相同Yi序列和相同的,Xi序列的值越小,对应的M也就越小,换个说法,对于相同的M和相同的质因数个数(就是Xi序列的元素个数),Xi越小,对就Yi中的元素的值就会越大,也就是M的因子总数也就越大,所以我们只需要质数中的前几个就可以了. 实际上只用前10个就足够了,也就是对于任意M,(M<=(2^32)-1),分解质因数后的互异质因数(就是相同的质因数只计一次)不会超过10个.因为取最小的10个质数,它们的乘积2*3*5*7...*29已经超过2^32了. 所以我们不再需要把1到N的所有数都计算一遍了,只要使 Zi = 2,3,5,7,....,29 然后给Yi赋不同的值,且要使这个组合所对应的M的值<=N. 在Yi的不同组合中,再来比较,这样我们就舍去了1到N中绝大部分不付合要求的数了,只要比较一小部分就可以了. 绝大部分数被舍去的原因是他的分解质因数的质因数有比较大质数,这是隐含在我们的算法之中的. 而且Zi中的数不是都要用到的.对于一些比较小的数,只要用前面的若干个就行了.这个在算法中的体现是后面几个不用的对应Yi中的值为0. 呵呵,总算说完了,嘴有点笨,不知你有没有明白. 以下是我的程序,程序太过粗糙了,不够优化还有不少Bug,大伙将就着看看吧. file://运行环境Vc++6.0 // pfan38_2.cpp : Defines the entry point for the console application.// #include "stdafx.h"#include <string.h>#include <math.h> int fac[10]={2,3,5,7,11,13,17,19,23,29};int num[10]={0};int mnum[10];int nfac=0;int max=0;__int64 cur=1;void add(int p){ int sum=1; __int64 t=1; for(int i=0;i<p;i++) { sum*=num[i]+1; t*=(__int64)pow(fac[i],num[i]); } if(sum>max||(sum==max&&t<cur)) { memcpy(mnum,num,10*sizeof(int)); nfac=p; max=sum; cur=t; }} void nSearch(__int64 n,int p,__int64 val){ __int64 t; for(num[p]=1;;num[p]++) { t=val*(__int64)pow(fac[p],num[p]); if(t>n) { num[p]--; if(num[p]==0) p--; add(p+1); break; } else if(p==9) { add(10); } else { nSearch(n,p+1,t); } }}int parr=0;void getarr(unsigned long arr[],int fac[],int num[],int len,int cur,__int64 val){ __int64 v; if(len==cur+1) { for(int i=0;i<=num[cur];i++) { arr[parr++]=(unsigned long)(val*(__int64)pow(fac[cur],i)); } } else { for(int i=0;i<=num[cur];i++) { v=val* (__int64)pow((double)fac[cur],(double)i); getarr(arr,fac,num,len,cur+1,v); } }}void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[]){ __int64 t; nSearch(n,0,1); parr=0; getarr(arr,fac,mnum,nfac,0,1); for(int i=0;i<max-1;i++) for(int j=i+1;j<max;j++) if(arr[i]>arr[j]) { t=arr[i]; arr[i]=arr[j]; arr[j]=(unsigned long)t; } *result=(unsigned long)cur; *count=max;} int main(int argc, char* argv[]){ unsigned long res,arr[10240],n; int cnt,i; n=4000000000; Search(n, &res,&cnt,arr); printf("\n%lu-%lu-%d--------------------------------------\n",n,res,cnt); for(i=0;i<cnt;i++) { printf("[%lu]",arr[i]); } return 0;}
评论