Problem 29 Distinct powers

Problem: Distinct powers

https://projecteuler.net/problem=29

nsider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

• 2²=4, 2³=8, 2⁴=16, 2⁵=32
• 3²=9, 3³=27, 3⁴=81, 3⁵=243
• 4²=16, 4³=64, 4⁴=256, 4⁵=1024
• 5²=25, 5³=125, 5⁴=625, 5⁵=3125

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 a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

分析

不同的幂。a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100，所有的不相等的结果的个数。

方法 直接遍历统计

最大为100¹⁰⁰ 为201位，这些都可以放到一个double类型里面（double的位数大约在300位）。使用set来存储，就可以去除重复。

C++标准库中没有大数处理函数，做OJ真是一大痛啊。不过话说回来，如果都象Python一样，那么OJ也就失去了很多意义了。这也是我这个系列一直坚持，每题都用C\C++和Python两种语言解决的原因。

CPP

使用 double 类型存储幂， 使用 STL set 确保不重复

#include <iostream>
#include <set>
#include <cmath>

int main()
{
    std::set<double> answer;
    for (double a = 2; a <= 100; a++)
        for (double b = 2; b <= 100; b++)
            answer.insert(pow(a,b));
    std::cout << answer.size();
    return 0;
}

感谢Darryl （Project Euler 论坛 第一页）。 没想到double类型这么能装，不过总觉得这么做还是有点点侥幸，如果不是2~100，改成2~1000呢？方法就不适用了。

Golang

因为float64的精度问题，golang中不能直接使用float64来解决本题的大数问题，需要使用大数包

package main

import (
    "fmt"
    "math/big"
)

func pow(a, b int) *big.Int {
    ret := big.NewInt(int64(a))
    bigA := big.NewInt(int64(a))

    for i:=2; i <= b; i++ {
        ret.Mul(ret, bigA)
    }
    return ret
}

func main() {

    answer := make(map[string]struct{}) // value 使用 struct{} 可以不占内存

    for a := 2; a <= 100; a++ {
        for b := 2; b <= 100; b++ {
            n := pow(a,b)
            answer[n.String()] = struct{}{}
        }
    }

    fmt.Println(len(answer))
}

Python

一行代码，使用set存储，自动去重，使用len()统计个数

print (len(set([a**b for a in range(2,101) for b in range(2,101)])))

答案

9183

作者：JarvisChu
原文链接：Problem 29 Distinct powers
版权声明：自由转载-非商用-非衍生-保持署名 | Creative Commons BY-NC-ND 3.0