题解：P7051 [NWRRC 2015] Distribution in Metagonia

· · 题解

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

题目大意

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

题目分析

观察题目：

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

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

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

那么所谓的其实就是两两互质其实就是让 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;
}