ProjectEuler Problem 29: Distinct powers

ProjectEuler Problem 29: Distinct powers

Mar 24, 2014
Coding
ProjectEuler

Problem 29: Distinct powers #

https://projecteuler.net/problem=29

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

2^2=4,  2^3=8,   2^4=16,  2^5=32
3^2>=9, 3^3=27,  3^4=81,  3^5=243
4^2=16, 4^3=64,  4^4=256, 4^5=1024
5^2=25, 5^3=125, 5^4=625, 5^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，其中 2 ≤ a ≤ 100， 2 ≤ b ≤ 100，所有的不相等的结果的个数。

方法 直接遍历统计 #

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

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

C++ #

使用 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