题解

这题题目要求 $2^{a_i}3^{b_i} \neq 2^{a_j}3^{b_j}$

那我们直接令所有的 $b = 0$，题目就变成了将一个 $n$ 转成 $2 ^ {a_i} + 2 ^ {a_{i + 1}} ...$，成了一个简单的二进制转换问题。

由于 $a_i$ 和 $b_i$ 的数量很有限，那么其 $a_ib_i$ 的组合数量也不多。

于是塔子哥猜测，出题人原本不是想考察这个。而是更像考察物品数量比较少，且背包容量比较大的，01背包恰好装满问题，这个可以用 最短路优化背包 的方法解决，但由于在笔试中这个难度有点超纲了，感兴趣的朋友可以自行了解。

AC代码

Python

T = int(input())
for _ in range(T):
    n = int(input())
    v = [(1 << i) for i in range(31, -1, -1) if (n >> i & 1)]
    print(len(v))
    print(*v)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        for (int t = 0; t < T; t++) {
            int n = scanner.nextInt();
            List<Integer> v = new ArrayList<>();
            for (int i = 31; i >= 0; i--) {
                if ((n >> i & 1) == 1) {
                    v.add(1 << i);
                }
            }
            System.out.println(v.size());
            for (int num : v) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> v;
        for (int i = 31; i >= 0; i--) {
            if ((n >> i) & 1) {
                v.push_back(1 << i);
            }
        }
        cout << v.size() << "\n";
        for (int num : v) {
            cout << num << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

问题描述

众所周知，任何一个数 $n$ 可以拆分为若干项，这些项是不同的，由 $2$ 的次幂和 $3$ 的次幂相乘之和组成，即：

且对于所有 $i$ 和 $j$ ，满足 $2^{a_i}3^{b_i} \neq 2^{a_j}3^{b_j}$

小红给你这个整数 $n$，希望你能找到这样两个长度为 $m$ 的序列 $A$ 和 $B$ 满足给出的方程($2^{a_1}3^{b_1},2^{a_2}3^{b_2},...,2^{a_m}3^{b_m}$)，并且按照由大到小的顺序依次输出。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T$（$1 < T < 100$），代表数据组数。每组测试数据描述如下：在一行上输入一个整数 $n$（$1 \leq n \leq 10^9$），代表给定的初始数字。

输出描述

对于每一组测试数据，第一行输出一个整数 $m$（$1 \leq m < 10^9$），代表序列的项数。第二行输出 $m$ 个不同的整数 $2^{a_1}3^{b_1},2^{a_2}3^{b_2},...,2^{a_m}3^{b_m}$，代表拆出的序列，并由大到小依次输出。

样例输入

5
10
15
123
3
321

样例输出

2
8 2
2
12 3
3
96 24 3
1
3
4
288 24 6 3

样例解释

1. 对于 $n = 10$，可以拆分为 $8 + 2$，其中 $8 = 2^3 \cdot 3^0$ 和 $2 = 2^1 \cdot 3^0$。
2. 对于 $n = 15$，可以拆分为 $12 + 3$，其中 $12 = 2^2 \cdot 3^1$ 和 $3 = 2^0 \cdot 3^1$。
3. 对于 $n = 123$，可以拆分为 $96 + 24 + 3$，其中 $96 = 2^5 \cdot 3^1$，$24 = 2^3 \cdot 3^1$ 和 $3 = 2^0 \cdot 3^1$。
4. 对于 $n = 3$，可以直接表示为 $3 = 2^0 \cdot 3^1$。
5. 对于 $n = 321$，可以拆分为 $288 + 24 + 6 + 3$，其中 $288 = 2^5 \cdot 3^2$，$24 = 2^3 \cdot 3^1$，$6 = 2^1 \cdot 3^1$ 和 $3 = 2^0 \cdot 3^1$。