题目29：a的b次方（2≤a,b≤100）中共有多少个不同的数？

欧拉计划

Distinct powers

Consider all integer combinations of a、b for :



If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by ?

题目：

考虑 下的所有整数组合：



如果将这些数字排序，并去除重复的，我们得到如下 15 个数字的序列：

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

下生成的序列中有多少个不同的项？

迷雾少年

9801项

1. #include <iostream>
   
2. #include <string>
   
3. #include <vector>
   
4. #include <iterator>
   
5. #include <algorithm>
   
6. using namespace std;
   
7. 
   
8. /* 结果容器 */
   
9. std::vector<string> myResult;
   
10. string Multiply(string s,int x)  //大数乘以整形数  
    
11. {  
    
12.         reverse(s.begin(),s.end());  
    
13.         int cmp=0;  
    
14.         for(int i=0;i<s.size();i++)  
    
15.         {  
    
16.                 cmp=(s[i]-'0')*x+cmp;  
    
17.                 s[i]=(cmp%10+'0');  
    
18.                 cmp/=10;  
    
19.         }  
    
20.         while(cmp)  
    
21.         {  
    
22.                 s+=(cmp%10+'0');  
    
23.                 cmp/=10;  
    
24.         }  
    
25.         reverse(s.begin(),s.end());  
    
26.         return s;  
    
27. }  
    
28. /* 求a的b次方 大数 */
    
29. string calc(int a,int b)
    
30. {
    
31.         string g("1");
    
32.        
    
33. 
    
34.         for (int z = 1; z<=b;z++)
    
35.         {
    
36.                  
    
37.                 g=Multiply(g,a);
    
38.         }
    
39.        
    
40.         return g;
    
41. }
    
42. int main()
    
43. {
    
44.         for (int a=2;a<=100;a++)
    
45.         {
    
46.                 for (int b=2;b<=100;b++)
    
47.                 {
    
48.                         myResult.push_back(calc(a,b));
    
49.                 }
    
50.         }
    
51.         std::cout<<myResult.size()<<endl;
    
52. 
    
53.         //去除重复
    
54.         unique(myResult.begin(),myResult.end());
    
55.         std::cout<<myResult.size()<<endl;
    
56.         return 0;
    
57.        
    
58. }

复制代码

愤怒的大头菇

1. list1 = []
   
2. for i in range(2,101):
   
3.       for j in range(2,101):
   
4.             temp = i**j
   
5.             if temp not in list1:
   
6.                   list1.append(temp)
   
7. 
   
8. print(len(list1))

复制代码

得到的结果是9183

愤怒的大头菇

迷雾少年 发表于 2016-8-29 16:19
9801项

没有去掉重复的项

jerryxjr1220

1. 9183
   
2. [Finished in 0.2s]
   
3. 
   
4. lst = []
   
5. for a in range(2,101):
   
6.         for b in range(2,101):
   
7.                 lst.append (a**b)
   
8. lst = set(lst)
   
9. print (len(lst))

复制代码

渡风

此代码使用matlab编程
Problem29所用时间为0.042795秒
Problem29的答案为9183

1. %% Problem29
   
2. %题目29:a的b次方(2≤a,b≤100)中共有多少个不同的数?
   
3. function Output=Problem29(Input)
   
4.   tic
   
5. if nargin==0
   
6. Input=100;
   
7. end
   
8. Total=(Input-1)^2;%总数有99*99个数
   
9. Sum=0;%出现多余数的数量
   
10. %现去掉多余的数
    
11. Rank2=2:100;%关于2 4 8 16 32 64
    
12. for ii=2:6
    
13.     Temp=ii*2:ii:ii*100;
    
14.     Rank2=union(Rank2,Temp);
    
15. end
    
16. Sum2=length(Rank2);
    
17. Rank3=2:100;%关于3 9 27 81
    
18. for ii=2:4
    
19.     Temp=ii*2:ii:ii*100;
    
20.     Rank3=union(Rank3,Temp);
    
21. end
    
22. Sum3=length(Rank3);
    
23. % 关于 5 25,6 36 ，7 49, 10 100
    
24. Sum_Other=(99+50)*4;
    
25. disp(Sum)
    
26. Output=Total-18*99+Sum2+Sum3+Sum_Other;                     
    
27. disp('此代码使用matlab编程')
    
28. disp(['Problem29所用时间为',num2str(toc),'秒'])
    
29. disp(['Problem29的答案为',num2str(Output)])
    
30. 
    

复制代码

余欲渔

1. >>> len(set([x**y for x in range(2,101)for y in range(2,101)]))
   
2. 9183
   
3. >>>

复制代码

99592938

1. list1=[]
   
2. for a in range(2,101):
   
3.     for b in range(2,101):
   
4.         list1.append(a**b)
   
5. print(len(set(list1)))

复制代码

9183
>>>

由我们主宰

1. public class DistinctPowers{
   
2.         public static void main(String[] args){       
   
3.                 int count = 0;
   
4.                 double[] result = new double[10000];
   
5.                 double n = 0;
   
6.                 for(int a = 2;a <= 100;a ++){
   
7.                         for(int b = 2;b <= 100;b ++){
   
8.                                 n = Math.pow(a,b);
   
9.                                 if(distinct(n,result,count)){
   
10.                                         result[count++] = n;
    
11.                                 }
    
12.                         }
    
13.                 }
    
14.                 System.out.println(count);
    
15.         }
    
16.         public static boolean distinct(double n,double[] result,int count){
    
17.                 boolean flag = true;
    
18.                 for(int i = 0;i < count;i ++){
    
19.                         if(result[i] == n){
    
20.                                 flag =false;
    
21.                         }
    
22.                 }
    
23.                 return flag;
    
24.         }
    
25. }

复制代码

9183

My_A

都是大佬

王小召

用时：0.1404009秒
a**b共有：9183 个不同值

import time

def get_result(n):
    result = []
    for a in range(2, n+1):
        for b in range(2, n+1):
            result.append(a**b)
    return result

print("用时：{}秒\na**b共有：{} 个不同值".format(time.process_time(), len(list(set(get_result(100))))))

永恒的蓝色梦想

1. from sys import stdout
   
2. stdout.write({a**b for a in range(2,101)for b in range(2,101)}.__len__().__str__())

复制代码

leon0149

直接用集合就行了呀
9183

1. array = set()
   
2. 
   
3. for i in range(2, 100 + 1):
   
4.     for j in range(2, 100 + 1):
   
5.         array.add(i ** j)
   
6. 
   
7. print(len(array))

复制代码

永恒的蓝色梦想

1. #include<iostream>
   
2. #include<cmath>
   
3. #include<set>
   
4. using namespace std;
   
5. 
   
6. 
   
7. int main() {
   
8.     ios::sync_with_stdio(false);
   
9.     set<double>vals;
   
10.     unsigned char i, j;
    
11. 
    
12.     for (i = 2; i <= 100; ++i) {
    
13.         for (j = 2; j <= 100; ++j) {
    
14.             vals.insert(pow(i, j));
    
15.         }
    
16.     }
    
17. 
    
18.     cout << vals.size() << endl;
    
19.     return 0;
    
20. }

复制代码

debuggerzh

9183

Process returned 0 (0x0)   execution time : 0.032 s
Press any key to continue.
参考http://www.cnblogs.com/WArobot的做法
思路：将底数化为最小底数（例如16=2*2*2*2，则16的最小底数为2），把幂化为最小底数的幂，用二维数组判重

1. #include<iostream>
   
2. #include<cstdio>
   
3. using namespace std;
   
4. 
   
5. const int M = 100;
   
6. const int M_EXP = 600;
   
7. int min_base[M+5] = {0};
   
8. int exp[M+5] = {0};
   
9. 
   
10. void ini_min_base(){
    
11.   for (int i = 2;i <= M;i++){
    
12.     if (min_base[i])  continue;
    
13.     min_base[i] = i;
    
14.     int p = 0;  //指数变量
    
15.     for (int j = i;j <= M;j *=i){
    
16.       min_base[j] = i;
    
17.       exp[j] = ++p;
    
18.     }
    
19.   }
    
20. }
    
21. 
    
22. int main(){
    
23.   int cnt = 0;
    
24.   int vis[M+5][M_EXP] = {0};
    
25.   ini_min_base();
    
26. 
    
27.   for (int a = 2;a <= M;a++){
    
28.     for (int b = 2;b <= M;b++){
    
29.       int a1 = min_base[a];
    
30.       int b1 = b * exp[a];
    
31.       if (!vis[a1][b1]) vis[a1][b1] = 1;
    
32.       //printf("%d %d %d\n",a1,b1,vis[a1][b1]);
    
33.     }
    
34.   }
    
35.   for (int i = 0;i < M+5;i++)
    
36.     for (int j = 0;j < M_EXP;j++) cnt += vis[i][j];
    
37.   cout << cnt << endl;
    
38.   return 0;
    
39. }
    

复制代码

有马_冬巳

1. start = time.time()
   
2. 
   
3. list = []
   
4. for a in range(2,101):
   
5.         for b in range(2,101):
   
6.                 if a**b not in list:
   
7.                         list.append(a**b)
   
8. 
   
9. print("共有%d个不同的项" %len(list))
   
10. 
    
11. end = time.time()
    
12. print("共用时%f秒" %(end - start))

复制代码

共有9183个不同的项
共用时0.449894秒

a1351468657

用python做这种大数计算就太简单了，觉得自己编程能力不错的可以用C语言试一下

guosl

这题不要被很大的次方吓坏了，双精度浮点数足够处理。

1. /*
   
2. 答案：9183
   
3. 耗时：0.0012099秒
   
4. */
   
5. #include <iostream>
   
6. #include <cmath>
   
7. #include <vector>
   
8. #include <algorithm>
   
9. using namespace std;
   
10. 
    
11. int main(void)
    
12. {
    
13.   vector<double> v;
    
14.   for (int a = 2; a <= 100; ++a)
    
15.   {
    
16.     for (int b = 2; b <= 100; ++b)
    
17.     {
    
18.       double d = pow(double(a), double(b));
    
19.       v.push_back(d);
    
20.     }
    
21.   }
    
22.   sort(v.begin(), v.end());
    
23.   auto itr = unique(v.begin(), v.end());
    
24.   int k = int(itr - v.begin());
    
25.   cout << k << endl;
    
26.   return 0;
    
27. }

复制代码

我看了前面的一些代码，许多人使用了set，其实这不是最优的，因为set的内部存储机制其实是一颗红黑树，每次插入都会引起树的重排，非常耗费时间。

Asss-whom

1. use rayon::prelude::*;
   
2. use num::bigint::ToBigUint;
   
3. use std::time::Instant;
   
4. use std::collections::BTreeSet;
   
5. 
   
6. fn main() {
   
7.     let now = Instant::now();
   
8.     let mut set = BTreeSet::new();
   
9.     let num = (2..101u32)
   
10.         .into_par_iter()
    
11.         .map(|a| {
    
12.             let a = a.to_biguint().unwrap();
    
13.             (2..101u32)
    
14.                 .into_par_iter()
    
15.                 .map(|b| a.pow(b))
    
16.                 .collect::<Vec<_>>()  
    
17.         })
    
18.         .collect::<Vec<_>>();
    
19.     for i in num {
    
20.         for j in i {
    
21.             set.insert(j);
    
22.         }
    
23.     }
    
24.     println!("cost {}ms.", now.elapsed().as_millis());
    
25.     println!("{}", set.len())
    
26. }
    

复制代码

cost 4ms.
9183

TLM

python
100根本测不到时间
9183
Time:0.0s
设置上限为1000
977358
Time:0.0029997825622558594s
时间复杂度应该是O(M*log(M))

1. import math
   
2. import time
   
3. st=time.time()
   
4. M=1000
   
5. # 同底去重，同底一定重复，不同底一定不会重复
   
6. al=list(range(M+1))
   
7. al[1]=0
   
8. nl=list()
   
9. n0=int(math.log(M)/math.log(2))
   
10. nl=[0]*n0
    
11. for a in al:
    
12.     if not a==0:
    
13.         i=1
    
14.         while a**i<=M:
    
15.             al[a**i]=0
    
16.             i=i+1
    
17.         # print((a,i))
    
18.         nl[i-2]=nl[i-2]+1
    
19. 
    
20. # a=a0**n; a**b=a0**(n*b) 转化为n*b有多少个，而且不会有大数
    
21. nbS=set()
    
22. num=0
    
23. nnum=0
    
24. for n in range(1,n0+1):
    
25.     # print(n)
    
26.     for b in range(2,M+1):
    
27.         if n*b not in nbS:
    
28.             nbS.add(n*b)
    
29.             num=num+1
    
30.     nnum=nnum+num*nl[n-1]
    
31. print(nnum)
    
32. print('Time:{}s'.format(time.time()-st))

复制代码