问题描述: 
正整数x的约数是能整除x的正整数。正整数x 的约数个数记为div(x)。例如,1,2,5,10 都是正整数10 的约数,且div(10)=4。设a 和b 是2 个正整数,a≤b,出a和b之间约数个数最多的数x。 
编程任务: 
对于给定的2个正整数a≤b,编程计算a 和 b 之间约数个数最多的数。 
数据输入: 
输入数据由文件名为的文本文件提供。文件的第1 行有2 个正整数 a和 b。 
结果输出: 
程序运行结束时,到a 和b之间约数个数最多的那个数及最多约数个数。
测试数据:【只给出最多约数个数, time limit: 1s】
[1, 36]                              9
[1000000, 2000000]          288
[999998999, 999999999]    1024
[1, 1000000000]                1344
[999999999, 1000000000]  56
[100, 1000000000]              1344
———————————————————————————————————————————————————
法一:主要就是查一个整数的约数个数的效率问题,首先想到的是 1-√x 遍历。逐个判断。但是效率太低。
[cpp] view plain copy
 print?
1.#include <iostream> 
2.#include <fstream> 
3.#include <ctime> 
4.#include <cmath> 
5.using namespace std; 
6. 
7.ifstream fin(""); 
8.ofstream fout(""); 
9. 
10.clock_t start,finish; 
11.double  total_time; 
12. 
13.int div(int n) 
14.
15.    int num = 0; 
16.    for (int i = 1; i < sqrt((float)n); i++) 
17.    { 
18.        if (n%i == 0) 
19.        { 
20.            num += 2; 
21.        } 
22.         
23.    } 
24.     
25.    if (n == (int)sqrt((float)n)*(int)sqrt((float)n)) 
26.    { 
27.        num ++; 
28.    } 
29.    return num; 
30.
31. 
32.int caculateMaxdiv(int a, int b) 
33.
34.    int maxNum = 0; 
35.    for (int i = a;i <= b;i++ ) 
36.    { 
37.        if ( maxNum < div(i)) 
38.        { 
39.            maxNum = div(i); 
40.        } 
41.    } 
42.    return maxNum; 
43.
44. 
45.int main() 
46.
47.    start = clock(); 
48.    int a,b; 
49.    fin>>a>>b; 
50.    fout<<caculateMaxdiv(a,b)<<endl; 
51.    finish = clock(); 
52. 
53.    total_time = (double)(finish - start)/CLOCKS_PER_SEC; 
54.    fout<<total_time<<" s"<<endl; 
55.    return 0; 
56.
法二:
思想:设正整数x的质因子分解为
x=p1^N1 × p2^N2 ×……pi^Ni
则 div(x)=(N1+1)(N2+1)……(Ni+1)
[cpp] view plain copy
 print?
1.#include<iostream> 
2.using namespace std; 
3.#define max Max 
4.const long MAXP = 100000; 
5.long prim[MAXP]; 
6.long max, numb, PCOUNT; //max存放最多约数个数,numb存放约数个数最多的数 
7.void primes();          //用筛选法产生质数存于prim数组中 
8.void search(long from, long tot, long num, long low, long up); 
9.int main() 
10.
11.    primes(); 
12.    long l, u; 
13.    cin >> l >> u; 
14.    if ((l == 1) && (u == 1)) 
15.    { 
16.        max = 1; 
17.        numb = 1; 
18.    } 
19.    else 
20.    { 
21.        max = 2; 
22.        numb = l; 
23.        search(1, 1, 1, l, u); 
24.    } 
25.    cout << max << endl << numb << endl; 
26.    system("pause"); 
字符串长度最大是多少27.    return 0; 
28.
29. 
30.void primes()   
31.
32.    bool get[MAXP+1]; 
33.    long i; 
34.    for (i = 2; i <= MAXP; i++) 
35.        get[i] = true
36.    for (i = 2; i <= MAXP; i++) 
37.        if (get[i]) 
38.        { 
39.            long j = i + i; 
40.            while (j <= MAXP)   
41.            { 
42.                get[j] = false
43.                j += i; 
44.            } 
45.        } 
46.        long ii, j; 
47.        for (ii = 2, j = 0; ii <= MAXP; ii++) 
48.            if (get[ii]) prim[++j] = ii; 
49.        PCOUNT = j; 
50.
51. 
52.void search(long from, long tot, long num, long low, long up) 
53.
54.    if (num >= 1) 
55.        if ( (tot > max) || ((tot == max) && (num < numb)) ) 
56.        { 
57.            max = tot; 
58.            numb = num; 
59.        } 
60.        if ((low == up) && (low > num)) search(from, tot*2, num*low, 1, 1); 
61.        for (long i = from; i <=PCOUNT; i++) 
62.        { 
63.            if (prim[i] > up) return;   
64.            else 
65.            { 
66.                long j = prim[i], x = low - 1, y = up, n = num, t = tot, m = 1; 
67.                while (true
68.                { 
69.                    m++; 
70.                    t += tot; 
71.                    x /= j; 
72.                    y /= j; 
73.                    if (x == y) break
74.                    n *= j; 
75.                    search(i+1, t, n, x+1, y); 
76.                } 
77.                m = 1 << m; 
78.                if (tot < max / m) return
79.            } 
80.        } 
81.
针对此方法的解析如下(源自网络):
本题的要求是,求出一个给定区间内的含约数最多的整数。
    首先明确一下如何求一个数的约数个数:若一个数N满足:N = A1N1 * A2N2 * A3N3 * …… * AmNm,则n的约数个数为(N1 + 1) (N2 + 1) (N3 + 1) …… (Nm + 1)。这是可以用乘法原理证明的。
    最浅显的算法是,枚举区间内的每个整数,统计它们的约数个数。这个算法很容易实现,但是时间复杂度却相当高。因为题目约定区间的最大宽度可以达到10^9的数量级,相当庞大。因此,在极限规模时,时间是无法忍受的。所以,我们需要尽量的优化时间。
    分析一下枚举的过程就会发现,如果我们枚举到两个数n和m*n(m为一相对于n较大的质数),那么我们将重复计算n的约数两次。据此,我们发现了枚举效率低的根本所在。为了解决这一重复,我们可以选取另一种搜索方法——以质因子为对象进行深度搜索。
    初始时,令number := 1,然后从最小的质数2开始枚举,枚举包含一个2、两个2……n个2
的情况……直至number * 2n大于区间的上限(max)。对于每种“2^k的情况”,令number := number * 2n,再枚举3的情况,然后,枚举5的情况、7的情况……方法相同。整个过程是一个深度搜索的过程。当number大于等于区间下限(min)时,我们就到了一个区间内的数,根据前面介绍的方法,可以得到它的约数个数。所有的区间内的数的约数个数的最大值就是我们要求的目标。

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。