Gym 100801D Distribution in Metagonia (数学思维题)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目：传送门。(需要下载PDF)

题意：t组数据，每组数据给定一个数ni(1 ≤ ni ≤ 10^18)，把ni拆成尽可能多的数，要求每个数的素因子只包含2和3，且这些数不能被彼此整除，输出一共能拆成多少个数，并输出这些数。

题解：根据题意 ni = 2^a0*3^b0*+2^a1*3^b1+........+2^ax*3^bx ，所以我们按照 ai升序 ， bi降序 的顺序求出每一个加数，这样会保证这些数不能被彼此整除。首先打表得知 3^40 会超过long long， 3^39 不会，先打出 3^39 的表存到数组中，然后循环遍历即可,代码中的 tmp表示的是2^ai 。

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

using namespace std;

typedef long long ll;

ll num3[];

ll ans[];

int main()

{

    freopen("distribution.in","r",stdin);

    freopen("distribution.out","w",stdout);

    num3[]=;

    for(int i=;i<=;i++)

    num3[i]=num3[i-]*;

    int t;

    scanf("%d",&t);

    while(t--)

    {

        memset(ans,,sizeof(ans));

        ll n,m;

        ll cnt=;

        scanf("%lld",&n);

        ll tmp=;

        int b=;

        while(n)

        {

            while(n%==&&n>) //n%2==0才是偶数

            {

                n/=;

                tmp*=;

            }

            while(b>=)

            {

                if(num3[b]>n)

                b--;

                else

                {

                    n-=num3[b];

                    ans[cnt++]=tmp*num3[b];

                    break;

                }

            }

            //cout<<"bb"<<n<<endl;

        }

        cout<<cnt<<endl;

        for(int i=;i<cnt-;i++)

        cout<<ans[i]<<" ";

        cout<<ans[cnt-]<<endl;

    }

    return ;

}