题目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项

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;

/* 结果容器 */
std::vector<string> myResult;
string Multiply(string s,int x)  //大数乘以整形数  
{  
        reverse(s.begin(),s.end());  
        int cmp=0;  
        for(int i=0;i<s.size();i++)  
        {  
                cmp=(s[i]-'0')*x+cmp;  
                s[i]=(cmp%10+'0');  
                cmp/=10;  
        }  
        while(cmp)  
        {  
                s+=(cmp%10+'0');  
                cmp/=10;  
        }  
        reverse(s.begin(),s.end());  
        return s;  
}  
/* 求a的b次方 大数 */
string calc(int a,int b)
{
        string g("1");
        

        for (int z = 1; z<=b;z++)
        {
                 
                g=Multiply(g,a); 
        }
        
        return g;
}
int main() 
{ 
        for (int a=2;a<=100;a++)
        {
                for (int b=2;b<=100;b++)
                {
                        myResult.push_back(calc(a,b));
                }
        }
        std::cout<<myResult.size()<<endl;

        //去除重复
        unique(myResult.begin(),myResult.end());
        std::cout<<myResult.size()<<endl;
        return 0;
        
} 

愤怒的大头菇

list1 = []
for i in range(2,101):
      for j in range(2,101):
            temp = i**j
            if temp not in list1:
                  list1.append(temp)

print(len(list1))

得到的结果是9183

愤怒的大头菇

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

没有去掉重复的项

jerryxjr1220

9183
[Finished in 0.2s]

lst = []
for a in range(2,101):
        for b in range(2,101):
                lst.append (a**b)
lst = set(lst)
print (len(lst))

渡风

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

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

余欲渔

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

99592938

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

9183
>>>

由我们主宰

public class DistinctPowers{
        public static void main(String[] args){        
                int count = 0;
                double[] result = new double[10000];
                double n = 0;
                for(int a = 2;a <= 100;a ++){
                        for(int b = 2;b <= 100;b ++){
                                n = Math.pow(a,b);
                                if(distinct(n,result,count)){
                                        result[count++] = n;
                                }
                        }
                }
                System.out.println(count);
        }
        public static boolean distinct(double n,double[] result,int count){
                boolean flag = true;
                for(int i = 0;i < count;i ++){
                        if(result[i] == n){
                                flag =false;
                        }
                }
                return flag;
        }
}

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))))))

永恒的蓝色梦想

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

leon0149

直接用集合就行了呀
9183

array = set()

for i in range(2, 100 + 1):
    for j in range(2, 100 + 1):
        array.add(i ** j)

print(len(array))

永恒的蓝色梦想

#include<iostream>
#include<cmath>
#include<set>
using namespace std;


int main() {
    ios::sync_with_stdio(false);
    set<double>vals;
    unsigned char i, j;

    for (i = 2; i <= 100; ++i) {
        for (j = 2; j <= 100; ++j) {
            vals.insert(pow(i, j));
        }
    }

    cout << vals.size() << endl;
    return 0;
}

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），把幂化为最小底数的幂，用二维数组判重

#include<iostream>
#include<cstdio>
using namespace std;

const int M = 100;
const int M_EXP = 600;
int min_base[M+5] = {0};
int exp[M+5] = {0};

void ini_min_base(){
  for (int i = 2;i <= M;i++){
    if (min_base[i])  continue;
    min_base[i] = i;
    int p = 0;  //指数变量
    for (int j = i;j <= M;j *=i){
      min_base[j] = i;
      exp[j] = ++p;
    }
  }
}

int main(){
  int cnt = 0;
  int vis[M+5][M_EXP] = {0};
  ini_min_base();

  for (int a = 2;a <= M;a++){
    for (int b = 2;b <= M;b++){
      int a1 = min_base[a];
      int b1 = b * exp[a];
      if (!vis[a1][b1]) vis[a1][b1] = 1;
      //printf("%d %d %d\n",a1,b1,vis[a1][b1]);
    }
  }
  for (int i = 0;i < M+5;i++)
    for (int j = 0;j < M_EXP;j++) cnt += vis[i][j];
  cout << cnt << endl;
  return 0;
}

有马_冬巳

start = time.time()

list = []
for a in range(2,101):
        for b in range(2,101):
                if a**b not in list:
                        list.append(a**b)

print("共有%d个不同的项" %len(list))

end = time.time()
print("共用时%f秒" %(end - start))

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

a1351468657

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

guosl

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

/*
答案：9183
耗时：0.0012099秒
*/
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

int main(void)
{
  vector<double> v;
  for (int a = 2; a <= 100; ++a)
  {
    for (int b = 2; b <= 100; ++b)
    {
      double d = pow(double(a), double(b));
      v.push_back(d);
    }
  }
  sort(v.begin(), v.end());
  auto itr = unique(v.begin(), v.end());
  int k = int(itr - v.begin());
  cout << k << endl;
  return 0;
}

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

Asss-whom

use rayon::prelude::*;
use num::bigint::ToBigUint;
use std::time::Instant;
use std::collections::BTreeSet;

fn main() {
    let now = Instant::now();
    let mut set = BTreeSet::new();
    let num = (2..101u32)
        .into_par_iter()
        .map(|a| {
            let a = a.to_biguint().unwrap();
            (2..101u32)
                .into_par_iter()
                .map(|b| a.pow(b))
                .collect::<Vec<_>>()  
        })
        .collect::<Vec<_>>();
    for i in num {
        for j in i {
            set.insert(j);
        }
    }
    println!("cost {}ms.", now.elapsed().as_millis());
    println!("{}", set.len())
}

cost 4ms.
9183

TLM

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

import math
import time
st=time.time()
M=1000
# 同底去重，同底一定重复，不同底一定不会重复
al=list(range(M+1))
al[1]=0
nl=list()
n0=int(math.log(M)/math.log(2))
nl=[0]*n0
for a in al:
    if not a==0:
        i=1
        while a**i<=M:
            al[a**i]=0
            i=i+1
        # print((a,i))
        nl[i-2]=nl[i-2]+1

# a=a0**n; a**b=a0**(n*b) 转化为n*b有多少个，而且不会有大数
nbS=set()
num=0
nnum=0
for n in range(1,n0+1):
    # print(n)
    for b in range(2,M+1):
        if n*b not in nbS:
            nbS.add(n*b)
            num=num+1
    nnum=nnum+num*nl[n-1]
print(nnum)
print('Time:{}s'.format(time.time()-st))