1906:Three powers

keyword

2進数　Java

概要

S = {3^i | i >= 0}の部分集合を要素の和で昇順に列挙したとき、n(<10^19)番目の部分集合を出力する問題。
nを2進数に直してビットの立っているものだけ拾ってくればよい。多倍長必須なのでJavaで。

import java.util.*;
import java.math.*;

class Main {

	public static void main(String args[]){
		Scanner in = new Scanner(System.in);
		for(;;){
			BigInteger n = in.nextBigInteger();
			if(n.equals(BigInteger.ZERO)) break;
			if(n.equals(BigInteger.ONE)){
				System.out.println("{ }");
				continue;
			}
			String bin = n.subtract(BigInteger.ONE).toString(2);
			Vector<BigInteger> ns = new Vector<BigInteger>();
			for(int i=0; i<bin.length(); i++){
				if(bin.charAt(bin.length()-1-i) == '1'){
					ns.add(new BigInteger("3").pow(i));
				}
			}
			
			System.out.print("{ ");
			for(int i=0; i<ns.size()-1; i++){
				System.out.print(ns.get(i) + ", ");
			}
			System.out.println(ns.get(ns.size()-1) + " }");
		}
	}

}