【2015-2016 ACM-ICPC, NEERC, Northern Subregional Contest D】---暑假三校训练

2015-2016 ACM-ICPC, NEERC, Northern Subregional Contest D

Problem D. Distribution in Metagonia Input file: distribution.in Output file: distribution.out Time limit: 2 seconds Memory limit: 256 megabytes There are one hundred noble families in the country of Metagonia, and each year some of these families receive several ritual cubes from the Seer of the One. The One has several rules about cube distribution: if a family receives at least one cube, every prime divisor of the number of cubes received should be either 2 or 3, moreover if one family receives a > 0 cubes and another family in the same year receives b > 0 cubes then a should not be divisible by b and vice versa. You are the Seer of the One. You know in advance how many cubes would be available for distribution for the next t years. You want to find any valid distribution of cubes for each of these years. Each year you have to distribute all cubes available for that year.

Input The first line of input file contains a single integer t — the number of years to come (1 ≤ t ≤ 1000). Each of the following t lines contains a single integer ni — the number of cubes to distribute in i-th year (1 ≤ ni ≤ 1018).

Output For each year i output two lines. The first line should contain mi — the number of families that would receive at least one cube in i-th year (1 ≤ mi ≤ 100). The second line should contain mi integers — the number of cubes received by each family. The sum of these numbers should be equal to ni .

Example

distribution.in

distribution.out

input：

output：

1 3

4 6

题意：输入一个数n，把n拆分成多个数的和，且每个数的素因子只有2和3，数之间不能整除；

思路：将n整除以2^t，使n变为奇数，找到3^k<=n，最大的k，则2^t*3^k为拆分后的一个数，则n-2^t*3^k必为一个偶数，再做相同的操作得到下一个拆分的数，直至n=0；

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

vector <LL> vec;
int main()
{
    //freopen("distribution.in","r",stdin);
    //freopen("distribution.out","w",stdout);
    int T;
    LL n;
    cin>>T;
    for(int i=0; i<T; i++)
    {
        vec.clear();
        cin>>n;
        for(int i=1; ; i++)
        {
            if(n <= 0)
                break;
            LL tp = n, sum = 1;
            while(tp)
            {
                if(tp & 1)
                    break;
                tp /= 2;
                sum *= 2;
            }   

            while(sum <= n)
                sum *= 3;
            sum /= 3;
            vec.push_back(sum);
            n -= sum;
        }
        cout<<vec.size()<<endl;
        for(int i=0; i<vec.size(); i++)
            cout<<vec[i]<<" ";
        cout<<endl;
    }
    return 0;
}