2012-07-09 20:32:02Morris
[UVA][Java] 10669 - Three powers
Problem B: Three powers
Consider the set of all non-negative integer powers of 3.
Consider the sequence of all subsets of S ordered by the value of the sum of their elements. The question is simple: find the set at the n-th position in the sequence and print it in increasing order of its elements.
Each line of input contains a number n, which is a positive integer with no more than 19 digits. The last line of input contains 0 and it should not be processed.
For each line of input, output a single line displaying the n-th set as described above, in the format used in the sample output.
Sample input
1 7 14 783 1125900981634049 0
Output for sample input
{ }
{ 3, 9 }
{ 1, 9, 27 }
{ 3, 9, 27, 6561, 19683 }
{ 59049, 3486784401, 205891132094649, 717897987691852588770249 }
轉二進制之後輸出 3^i
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
BigInteger[] pow = new BigInteger[100];
pow[0] = new BigInteger("1");
for(int i = 1; i < 100; i++)
pow[i] = pow[i-1].multiply(BigInteger.valueOf(3));
while(cin.hasNextLong()) {
long n = cin.nextLong();
if(n == 0)
break;
n--;
System.out.print("{");
int cnt = 0, flag = 0;
while(n != 0) {
if(n%2 == 1) {
if(flag != 0)
System.out.print(",");
System.out.print(" " + pow[cnt].toString());
flag = 1;
}
cnt ++;
n = n/2;
}
System.out.println(" }");
}
}
}