自动搬运

查看原文

来自洛谷，原作者为

	Shuhang_JOKER1 一只可爱的程序猿

搬运于2025-08-24 22:26:13，当前版本为作者最后更新于2025-08-03 09:49:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

此篇题解比较简单，面向新手群体，大佬勿喷

题目大意

给定一个整数 $n$，要将 $n$ 分解成若干个只含质因数 $2$ 和 $3$ 的数的和，并且这若干个数两两之间没有倍数关系，求其中一种方案。

题目分析

观察题目：

1.题目中“所有质因数应该是 $2$ 或 $3$”其实就是除了 $2$ 和 $3$，这个数不能有其它的质因子。

2. 其实就是要将分解的每个数 $sum=2^x\times 3^y$，让我们求其中一种分解方案。

3. 观察题目，发现分解的数两两互质。

那么所谓的其实就是两两互质其实就是让 $x$ 单调递增，$y$ 单调递减，或者 $x$ 单调递减，$y$ 单调递增，我们不妨让 $x$ 单调递增，$y$ 单调递减。

题目解答

想要让 $x$ 单调递增，我们考虑将 $n$ 的值赋值到另一个变量 $m$ 里，每次如果 $m$ 是偶数就让 $x$ 加 $1$，$m$ 再除以 $2$，而 $y$ 则能加 $1$ 就加 $1$（前提是 $3^y\le m$）。

为什么是这样呢？我们考虑操作后剩下来的数 $m-3^y$ 是不是偶数。$3$ 的幂次肯定是奇数，如果 $m-3^y$ 是奇数，那么整体是偶数，因为以前已经将 $m$ 除到了奇数，所以不可能出现这种情况，所以 $m-3^y$ 必定是奇数。

既然 $m-3^y$ 必定是奇数，那么总体是偶数，下一轮还剩的 $n-sum$ 中情况其实就是 $2^x×(m-3^y)$，既然 $m-3^y$ 是偶数，那么其实就是给下一轮的 $x$ 增加了，也就是说 $x$ 至少变成了 $x+1$，这样就满足 $x$ 单调递增这条性质了。

代码（求 $x$）：

while(m%2==0){//m 是偶数就继续
    m/=2;//缩小 m
    sum1*=2;//x 加 1
}

接下来考虑 $y$，为什么 $y$ 单调递减呢？因为每一轮 $n$ 都在减少（剩下来的少了），而 $x$ 却越来越多。但有的人就说了，$x$ 只会多乘 $2$，$y$ 除以的数可是 $3$ 啊，$2<3$，不应该可能会不变吗？

那我们不妨计算一下，假设 $x$ 等于上一个 $x$ 再加 $1$，那么计算 $y$ 前剩下的 $m$ 就是 上一个的 $(m-3^y)/2$，因为剩下的 $(m-3^y)$ 的加上求的 $3^y$ 肯定小于 $3^{(y+1)}$，可得 $(m-3^y)$ 小于 $3^y×2$，那么 $(m-3^y)/2$ 一定小于 $3^y$。

这样既满足了 $x$ 单调递增，又满足了 $y$ 单调递减。

代码（求 $y$）：

while(sum2 * 3 <= n){//sum 能乘就继续
    sum2 *= 3;//y 加 1

然后在外面套个 while 循环，只要 $n>0$，就继续，否则就是分完了，不继续了。

最后，注意本题要开 long long！

接下来看代码：

#include<bits/stdc++.h>
#define int long long//注意要开 long long
using namespace std;
int t,n;
void outs(vector<int> v){
	cout<<v.size()<<'\n';
	for(int i=0;i<v.size();i++)
		cout<<v[i]<<' ';
	cout<<'\n';
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--) {
		cin>>n;
		vector<int>v;
		while(n>0) {//如果 n > 0 就继续
			int sum1=1,sum2=1,m=n;//sum 和 m
			while(m % 2 == 0){//m 是偶数就继续
				m /= 2;//缩小 m
				sum1 *= 2;//x 加 1
			}
			while(sum2 * 3 <= m)//sum 能乘就继续
				sum2 *= 3;//y 加 1
			v.push_back((sum1*sum2));//加入答案
			n -= (sum1*sum2);//更新 n
		}
		outs(v);//输出
	}
	return 0;
}