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

Fractions involving the number of different ways a number can be expressed as a sum of powers of 2 题号:175 难度: 70 中英对照

Define f(0)=1 and f(n) to be the number of ways to write n as a sum of powers of 2 where no power occurs more than twice.

For example, f(10)=5 since there are five different ways to express 10:
10 = 8+2 = 8+1+1 = 4+4+2 = 4+2+2+1+1 = 4+4+1+1

It can be shown that for every fraction p/q (p>0, q>0) there exists at least one integer n such that
f(n)/f(n-1)=p/q.

For instance, the smallest n for which f(n)/f(n-1)=13/17 is 241.
The binary expansion of 241 is 11110001.
Reading this binary number from the most significant bit to the least significant bit there are 4 one's, 3 zeroes and 1 one. We shall call the string 4,3,1 the Shortened Binary Expansion of 241.

Find the Shortened Binary Expansion of the smallest n for which
f(n)/f(n-1)=123456789/987654321.

Give your answer as comma separated integers, without any whitespaces.

Solution

由169题,可以看到: 当$n$为奇数时,设$n=2k+1$,有$f(n)=f(k),f(n-1)=f(k)+f(k-1)$,且$f(n)< f(n-1)$。 当$n$为偶数时,设$n=2k$,有$f(n)=f(k)+f(k-1),f(n-1)=f(k-1)$,且$f(n)>f(n-1)$。 则由等式: $$\frac{p}{q}=\frac{f(n)}{f(n-1)}$$ 可以推出: 若$p< q$ 则$n$是奇数,有 $$\frac{p}{q-p}=\frac{f(k)}{f(k-1)}$$ 若$p> q$ 则$n$是偶数,有 $$\frac{p-q}{q}=\frac{f(k)}{f(k-1)}$$ 这与欧几里德算法很相似,只需要辗转相除即可。 具体过程如下: 1. $p/q=123456789/987654321=13717421/109739369$,由于$p< q$,则$n$为奇数,$q=p\times 8+1$,因此先写下$8$个$1$,令$q=1$ 2. $p/q=13717421/1$,由于$p>q $,则$n$为偶数,写下$13717420$个0后,$p=q=1$, 3. 则再写下一个$1$

Code

import java.math.BigInteger;

public final class p175 {
    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() {
    	// if n is odd
    	//   f(n)=f(n/2) < f(n-1)=f(n/2)+f(n/2-1)
    	// if n is even
    	//   f(n)=f(n/2)+f(n/2-1) > f(n-1)=f(n/2-1)
    	// that means:
    	// if q>p then n is odd  and p/q=f(n)/f(n-1) => p/(q-p)=f(n/2)/f(n/2-1)
    	// if q<p then n is even and p/q=f(n)/f(n-1) => (p-q)/q=f(n/2)/f(n/2-1)
    	// if and only if p=q=1 then n=1
    	final long a=123456789,b=987654321;
    	String res=solve(a,b);
    	res=res.substring(0,res.length()-1);
    	return res;
    }
    
    static String solve(long a,long b){
    	long c=gcd(a,b);
    	a/=c;b/=c;
    	String res;
    	if(a==1&&b==1) res="1";
    	else{
	    	long r=0,newa,newb;
	    	if(a<b){
	    		newa=a;
	    		newb=b%a;
	    		r=b/a;//r个1
	    		if(newb==0){
	    			newb=1;
	    			r--;
	    		}
	    	}
	    	else{
	    		newa=a%b;
	    		newb=b;
	    		r=a/b;//r个0
	    		if(newa==0){
	    			newa=1;
	    			r--;
	    		}
	    	}
			res=solve(newa,newb)+r;
    	}
		return  res+",";
    }

 	public static long gcd(long x, long y) {
 		while (y != 0) {
 			long z = x % y;
 			x = y;
 			y = z;
 		}
 		return x;
 	}
    static long get(long n){
		BigInteger bi=BigInteger.valueOf(n);
		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;
    }
}
1,13717420,8
0ms