一个算法题，应该有很多种方法可以得到结果

ccjjhua

应该说是只有2,3,5（质因子）的数，本题才有意义，不然的话4=2^2,则4就含有4的因子了。
只有2,3,5(质)因子的数应该只能表示为n=2^x*3^y*5^z(x,y,z为非副整数且x,y,z至少有一个>0）,1不符合题意，不能算是解的特例，

ccjjhua

应该说是只有2,3,5（质因子）的数，本题才有意义，不然的话4=2^2,则4就含有4的因子了。
只有2,3,5(质)因子的数应该只能表示为n=2^x*3^y*5^z(x,y,z为非副整数且x,y,z至少有一个>0）,1不符合题意，不能算是解的特例，

connet

一位数据肯定是乘2,3,5之中一位?  4, 6, 9, 呢？ 难道满足？

wxp19831104

能不能详细解释一下这句话：

通过对和的估计,可以得到C<= exp(三次根号(6*log2*log3*log5*N));取N=1500, 得到C<=4650268755.0

yuxh

我把第一种方法进行优化,可以得到O(n)时间、O(1)空间的算法

1. int i_log(long long m, int n)
   
2. {
   
3.     int i;
   
4.     for(i=0; m >= n; i++) m /= n;
   
5.     return i;
   
6. }
   
7. long long i_pow(int m, int n)
   
8. {
   
9.     long long val;
   
10.     for(val = 1L; n > 0; n--) val *= m;
    
11.     return val;
    
12. }
    
13. long long get_val(int i, int j, int k)
    
14. {
    
15.     int x;
    
16.     int val = 1;
    
17.     for(x = 0; x < i; x++) val *= 2;
    
18.     for(x = 0; x < j; x++) val *= 3;
    
19.     for(x = 0; x < k; x++) val *= 5;
    
20.     return val;
    
21. }
    
22. int count_n(long long m)
    
23. {
    
24.     int i, j, n = 0, x;
    
25.     for(i=0; i<=i_log(m, 2); i++) {
    
26.         x = i_log(m/i_pow(2,i), 3);
    
27.         for(j=0; j<=x; j++)
    
28.             n += i_log(m/i_pow(2,i)/i_pow(3,j), 5) + 1;
    
29.     }
    
30.     return n;
    
31. }
    
32. long long get_max_c(long long m)
    
33. {
    
34.     int i, j, n = 0, x;
    
35.     long long c = 0, t;
    
36.     for(i=0; i<=i_log(m, 2); i++) {
    
37.         x = i_log(m/i_pow(2,i), 3);
    
38.         for(j=0; j<=x; j++) {
    
39.             t = get_val(i, j, i_log(m/i_pow(2,i)/i_pow(3,j), 5));
    
40.             if( t > c) c = t;
    
41.         }
    
42.     }
    
43.     return c;
    
44. }
    
45. long long get_c(long long max, int n)
    
46. {
    
47.     int max_n = count_n(max), tmp;
    
48.     long long min = 0, mid;
    
49.     while(max_n > n) {
    
50.         mid = (max + min) / 2;
    
51.         if((tmp = count_n(mid)) < n)
    
52.             min = mid;
    
53.         else {
    
54.             max = mid;
    
55.             max_n = tmp;
    
56.         }
    
57.     }
    
58.     return get_max_c(max);
    
59. }
    
60. 
    
61. int main()
    
62. {
    
63.     printf("%lld\n", get_c(4650268755LL, 1500));
    
64. }
    

复制代码

这个的好处是没用到数组，空间占用小

yuxh

原帖由 wxp19831104 于 2006-5-10 10:10 发表
能不能详细解释一下这句话：

通过对和的估计,可以得到C<= exp(三次根号(6*log2*log3*log5*N));取N=1500, 得到C<=4650268755.0

如图：

jakieyoung

我的想法于你们不一样。可以将i，j，k看做一组数，它对应一个形式为2^i*3^j*5^k的数
即f(i,j,k)=2^i*3^j*5^k.
n    i,j,k
1   0,0,0
2   1,0,0
3   0,1,0
4   2,0,0
5   0,0,1
6   1,1,0
......
只要找出第1500组这样的数就可以了。
用方法找出前一组（或前N组）和后一组的关系即可。

[ 本帖最后由 jakieyoung 于 2006-5-12 17:31 编辑 ]