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

Exploring the number of different ways a number can be expressed as a sum of powers of 2 题号:169 难度: 50 中英对照

Define f(0)=1 and f(n) to be the number of different ways n can be expressed as a sum of integer powers of 2 using each power no more than twice.

For example, f(10)=5 since there are five different ways to express 10:

1 + 1 + 8
1 + 1 + 4 + 4
1 + 1 + 2 + 2 + 4
2 + 4 + 4
2 + 8

What is f(1025)?

Solution

因为同一个$2^k$只能最多使用2次。 举例考虑一个二进制下的数$1010_2=10_{10}$,则至少可以被分解为$1000_2+10_2=(2^3)_{10}+(2^1)_{10}$。 我们考虑从大到小分解$(2^k)_{10}$,即要么不分解,要么分解为两个$(2^{k-1})_{10}$。 我们维护两个部分的答案$a$和$b$分别表示分解和不分解当前数位的方案数,则显然的初始值是$a=1$和$b=0$。 从高位向低位枚举二进制下的$n$:遇到$1$则表示可分解可不分解,不分解的方案数在$a$中保存着,于是将$b+=a$增加上已有的这些方案即可;遇到$0$则不需要分解,将$a+=b$更新不分解的答案即可。 值得注意的是,最后一位表示$2^0=1$,不能分解。 最后的答案是$a$保存的值。

Code

import java.math.BigInteger;

public final class p169 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }
	
    static public String run() {
		BigInteger bi = new BigInteger("10000000000000000000000000");
		long a = 1;
		long b = 0;
		for (int i = bi.bitLength()-1; i >=0; i--) {
			if (bi.testBit(i)){
				b += a;
			}
			else{
				a += b;
			}
		}
		return a+"";
	}
}
178653872807
1ms