华师一附中OI组

标题: [L,R]中哪个数的约数最多 [打印本页]

---

作者: diggersun    时间: 2016-8-7 14:49
标题: [L,R]中哪个数的约数最多
//求10^5内谁的约数最多
#include<iostream>
using namespace std;
int n;
int p[15]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}; //前7个质数的乘积已经大于10^5说明不可能有超过7个质因子
long long   maxs=1; //约数最多的那个数
int maxk=0;//最多的约数个数
void mysearch(int i,long  long s,long long  j,long long  k)
//i表示深度（搜索到了第几个质因子）
//s表示当前因子最多的那个数字
//j表示最多含有多少个第i层的因子
//k表示当前最多因子的个数
{
    int jj;
    if(i>=9) return;
    if (k>maxk){maxs=s;maxk=k; cout<<maxs<<' '<<maxk<<endl;}
    for (jj=1;jj<=j;jj++)
    {
        s=s*p[i];
        if (s<=n) mysearch(i+1,s,jj,k*(jj+1));
    }
}
int main()
{
   n=99999999;
   mysearch(0,1,30,1);
   cout<<maxs<<' '<<maxk;
}

---

作者: hr567    时间: 2016-8-9 08:41

1. //CodeVS数据有错
   
2. #include <iostream>
   
3. using namespace std;
   
4. const int pNum = 20;
   
5. const int p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 71};
   
6. int l, r;
   
7. int ans = 1 << 30;
   
8. int now = 0;
   
9. void dfs(int i, int s, long long n)
   
10. {
    
11.     if (n > r || i >= 12)
    
12.         return;
    
13.     if (n >= l)
    
14.         if ((s == now && n < ans) || s > now)
    
15.         {
    
16.             ans = n;
    
17.             now = s;
    
18.         }
    
19.     int k = 1;
    
20.     while (n < r)
    
21.     {
    
22.         dfs(i+1, s * k, n);
    
23.         ++k;
    
24.         n *= p[i];
    
25.     }
    
26. }
    
27. int cal(int n)
    
28. {
    
29.     int i = 2, k = 1, sum = 1;
    
30.     while (n != 1)
    
31.     {
    
32.         if (n % i == 0)
    
33.         {
    
34.             n /= i;
    
35.             ++k;
    
36.         }
    
37.         else
    
38.         {
    
39.             sum *= k;
    
40.             k = 1;
    
41.             ++i;
    
42.         }
    
43.     }
    
44.     sum *= k;
    
45.     return sum;
    
46. }
    
47. int main()
    
48. {
    
49.     cin >> l >> r;
    
50.     if (r - l <= 100000)
    
51. //此处应加判断，区间较小时直接计算，否则有可能错解，如l=r且为两大质数之积
    
52.         for (int i = l; i <= r; ++i)
    
53.         {
    
54.             int x = cal(i);
    
55.             if (x > now)
    
56.             {
    
57.                 now = x;
    
58.                 ans = i;
    
59.             }
    
60.         }
    
61.     else
    
62.         dfs(0, 1, 1);
    
63.     cout << "Between " << l << " and " << r << ", " << ans << " has a maximum of " << now << " divisors." << endl;
    
64.     return 0;
    
65. }
    

复制代码

---

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

Powered by Discuz! X3.2