华师一附中OI组

标题: 1-m中那个数的约数最多 [打印本页]

---

作者: admin    时间: 2018-5-1 14:38
标题: 1-m中那个数的约数最多
1、最简单和直观的方法是对于每个数字，统计他的约数的个数，记录约数最多的数，这样复杂度大约在n2级别，优化下，也大约在nlnn。（想想怎么优化）
2、直接生成法，任何数都可以表示成一个唯一分解式子 N=2^x1*3^x2*5^x3******K^Xk。其中2,3,5，**K都是质数，而且k不会太大，然后x1---xk的范围也很好确定，搜索不断调整就是。

---

作者: admin    时间: 2018-5-1 14:38

1. #include<iostream>
   
2. using namespace std;
   
3. int l,r,s,i,j,maxy,maxi;
   
4. int main()
   
5. {
   
6.     cin>>l>>r;
   
7.     maxx=maxy=0;
   
8.     for (i=l; i<=r; i++)
   
9.     {
   
10.         s=0;
    
11.         for (j=1; j<=i; j++)
    
12.             if (i%j==0) s=s+1;
    
13.         if (s>maxy){maxy=s;maxi=i;}  //约数多少个，这个数字是几都要记录下来
    
14.     }
    
15.     cout<<maxy<<' '<<maxi;
    
16.     return 0;
    
17. }
    

复制代码

---

作者: admin    时间: 2018-5-1 14:39

1. #include<iostream>
   
2. using namespace std;
   
3. int n;
   
4. int p[15]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}; //前7个质数的乘积已经大于10^5说明不可能有超过7个质因子
   
5. long long   maxs=1; //约数最多的那个数
   
6. int maxk=0;//最多的约数个数
   
7. void mysearch(int i,long  long s,long long  j,long long  k)
   
8. //i表示深度（搜索到了第几个质因子）
   
9. //s表示当前因子最多的那个数字
   
10. //j表示最多含有多少个第i层的因子
    
11. //k表示当前最多因子的个数
    
12. {
    
13.     int jj;
    
14.     if(i>=9) return;
    
15.     if (k>maxk){maxs=s;maxk=k; cout<<maxs<<' '<<maxk<<endl;}
    
16.     for (jj=1;jj<=j;jj++)
    
17.     {
    
18.         s=s*p[i];
    
19.         if (s<=n) mysearch(i+1,s,jj,k*(jj+1));
    
20.     }
    
21. }
    
22. int main()
    
23. {
    
24.    n=100000;
    
25.    mysearch(0,1,30,1);
    
26.    cout<<maxs<<' '<<maxk;
    
27. }
    

复制代码

---

作者: ZMQ    时间: 2018-5-26 21:27
提示: 作者被禁止或删除 内容自动屏蔽

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2