2013
11-12

Non-divisible 2-3 Power Sums

Every positive integer N can be written in at least one way as a sum of terms of the form (2a)(3b) where no term in the sum exactly divides any other term in the sum. For example:

1 = (20)(30)
7 = (22)(30) + (20)(31)
31 = (24)(30) + (20)(32) + (21)(31) = (22) + (33)

Note from the example of 31 that the representation is not unique.

Write a program which takes as input a positive integer N and outputs a representation of N as a sum of terms of the form (2a)(3b).

The first line of input contains a single integer C (1 ≤ C ≤ 1000) which is the number of datasets that follow.

Each dataset consists of a single line of input containing a single integer N (1 ≤ N < 231), which is the number to be represented as a sum of terms of the form (2a)(3b).

For each dataset, the output will be a single line consisting of: The dataset number, a single space, the number of terms in your sum as a decimal integer followed by a single space followed by representations of the terms in the form [<2 exponent>,<3 exponent>] with terms separated by a single space. <2 exponent> is the power of 2 in the term and <3 exponent> is the power of 3 in the term.

6
1
7
31
7776
531441
123456789

1 1 [0,0]
2 2 [2,0] [0,1]
3 3 [4,0] [0,2] [1,1]
4 1 [5,5]
5 1 [0,12]
6 8 [3,13] [4,12] [2,15] [7,8] [9,6] [0,16] [10,5] [15,2]

/* @author: */
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n, i, k, t, tt, p, count = 0;
tt=sc.nextInt();
while(( tt-- )!=0) {
n=sc.nextInt();
int a[]=new int[100];
int b[]=new int[100];
k = 0;
p = 0;
while( n!=0 ) {
for( ; (n&1)==0; p++, n>>=1 )
;
for( t=1, i=0; t*3<=n; t*=3,i++ )
;
a[k] = p;
b[k] = i;
n -= t;
k++;
}
System.out.printf( "%d %d", ++count, k );
while(( k--)!=0 )
System.out.printf( " [%d,%d]", a[k], b[k] );
System.out.printf( "\n" );
}
}
}

1. 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法

3. 第一句可以忽略不计了吧。从第二句开始分析，说明这个花色下的所有牌都会在其它里面出现，那么还剩下♠️和♦️。第三句，可以排除2和7，因为在两种花色里有。现在是第四句，因为♠️还剩下多个，只有是♦️B才能知道答案。

4. 在方法1里面：

//遍历所有的边，计算入度
for(int i=0; i<V; i++)
{
degree = 0;