欧拉计划 发表于 2015-4-23 23:20:38

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

本帖最后由 欧拉计划 于 2023-10-18 02:14 编辑

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

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

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

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-'0')*x+cmp;
                s=(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;
       
}

愤怒的大头菇 发表于 2016-9-1 16:18:29

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-9-1 16:20:17

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

没有去掉重复的项

jerryxjr1220 发表于 2016-9-21 20:58:29

9183


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

渡风 发表于 2017-1-23 20:09:57

此代码使用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)])

余欲渔 发表于 2017-3-2 13:44:31

>>> len(set())
9183
>>>

99592938 发表于 2017-3-18 22:03:23

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

由我们主宰 发表于 2018-7-29 08:42:40

public class DistinctPowers{
        public static void main(String[] args){       
                int count = 0;
                double[] result = new double;
                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 = 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 == n){
                                flag =false;
                        }
                }
                return flag;
        }
}
9183

My_A 发表于 2019-3-23 22:54:18

都是大佬

王小召 发表于 2019-6-12 14:18:27

用时：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))))))

永恒的蓝色梦想 发表于 2019-7-22 20:39:27

本帖最后由 永恒的蓝色梦想 于 2020-6-19 10:46 编辑

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

leon0149 发表于 2020-5-17 11:32:19

直接用集合就行了呀
9183
array = set()

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

print(len(array))

永恒的蓝色梦想 发表于 2020-6-14 20:44:59

#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 发表于 2020-8-3 17:06:01

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 = {0};
int exp = {0};

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

int main(){
int cnt = 0;
int vis = {0};
ini_min_base();

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

有马_冬巳 发表于 2020-10-22 10:56:47

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 发表于 2021-3-13 18:06:51

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

guosl 发表于 2022-1-2 22:17:39

本帖最后由 guosl 于 2022-1-2 22:21 编辑

这题不要被很大的次方吓坏了，双精度浮点数足够处理。{:10_257:}
/*
答案：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 发表于 2022-8-8 12:57:49

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 发表于 2023-1-13 19:49:06

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=0
nl=list()
n0=int(math.log(M)/math.log(2))
nl=*n0
for a in al:
    if not a==0:
      i=1
      while a**i<=M:
            al=0
            i=i+1
      # print((a,i))
      nl=nl+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
print(nnum)
print('Time:{}s'.format(time.time()-st))
页: [1]
查看完整版本: 题目29：a的b次方（2≤a,b≤100）中共有多少个不同的数？