当前位置:首页 » Project Euler » 详细页

Powerful digit counts 题号:63 难度: 5 中英对照

The 5-digit number, 16807=75, is also a fifth power. Similarly, the 9-digit number, 134217728=89, is a ninth power.

How many n-digit positive integers exist which are also an nth power?

Solution

我们要找的整数满足条件: $$ 10^{n-1} \leq x^n < 10^n $$ 我们有: $$ x^n < 10^n \rightarrow x \leq 9 $$ $$ 10^{n-1} \leq x^n ~ \leftrightarrow ~ n-1 \leq log(x)n ~ \leftrightarrow ~ 10^\frac{n-1}{n} \leq x $$ 即 $~x~$ 有上界和下界: $$ 10^\frac{n-1}{n} \leq x \leq 9 $$ 也就是说对一个给定的$~n~$,满足条件的$~x~$的数目是 $$ 10 - \lceil 10^\frac{n-1}{n} \rceil $$ 因此只要对 $~n~$ 进行迭代即可求解。

Code


import java.math.BigInteger;

public final class p056 {

    public static void main(String[] args) {
        long start = System.nanoTime();
        long result = run();
        long end = System.nanoTime();
        System.out.println(result);
        System.out.println((end - start) / 1000000 + "ms");
    }

    public static long run() {
        int count = 0;
        int x =0;
        int n=1;
        while(x<=9){
            x = (int)Math.ceil(Math.pow(10,(n-1.0)/n));
            count += 10 - x;
            n++;
        }
        return count;
    }
}
49
0ms