https://ac.nowcoder.com/acm/contest/318/E

C++版本一

题解：

这是一个考验数学思维的题目。
当满足条件的集合内只有两个数的时候，要么n=a*a，要么n=a*(a-1)，我们可以直接对n进行开根号运算，令cnt1 = ceil(sqrt(n))，cnt2 = floor(sqrt(n))，然后判断cnt1 *cnt2 是否等于n即可。当满足条件的集合内有大于等于三个数的时候，我们可以知道n = a * a * a * ... * (a-1)*...*(a-1)。当a取到最大值时，应该满足n = a * a * a，而n是小于等于1e18的，所以我们可以知道a是小于等于1e6的，所以我们就可以暴力对a进行枚举了，每次验证一下是否合法即可。
对于输出“-1”的情况，也就只有当n=1，或者n=2^k的时候会成立，此时n可以分解为k个2和无数个1相乘的形式，故有无数个集合。最后再按要求处理一下输出就可以了。

#include <bits/stdc++.h>
#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pb push_back
#define MP make_pair
#define lowbit(x) x&-x
#define clr(a) memset(a,0,sizeof(a))
#define _INF(a) memset(a,0x3f,sizeof(a))
#define FIN freopen("in.txt","r",stdin)
#define IOS ios::sync_with_stdio(false)
#define ***(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int>pii;
const int MX = 1e6 + 5;
const int N = 1e6;

vector<ll> ver[MX];

int main() {
    // FIN;
    int cas = 1;
    ll n; int T;
    cin >> T;
    while (T--) {
        scanf("%lld", &n);
        bool flag = 1;
        for (int i = 0; i < 64; i++) {
            if ((1ll << i) == n) {
                flag = 0;
                break;
            }
        }
        printf("Case #%d:\n", cas++);
        if (!flag) {
            puts("-1");
            continue;
        }
        ver[0].pb(n);
        int num = 1;
        ll cnt = (ll)sqrt(n);
        if (cnt * cnt == n) {
            ver[num].pb(cnt);
            ver[num].pb(cnt);
            num++;
        }
        if (cnt * (cnt + 1) == n) {
            ver[num].pb(cnt);
            ver[num].pb(cnt + 1);
            num++;
        }
        for (int i = 2; i <= N; i++) {
            if (i == cnt) continue;
            if ((ll)i * i * i > n) break;
            ll now = n;
            int num1 = 0, num2 = 0;
            if (now % i == 0) {
                while (now % i == 0) now /= i, num1++;;
                while (now % (i + 1) == 0) now /= (i + 1), num2++;
                if (now == 1 && num1 > 0) {
                    for (int j = 0 ; j < num1; j++) ver[num].pb(i);
                    for (int j = 0; j < num2; j++) ver[num].pb(i + 1);
                    num++;
                }
            }
        }
        for (int i = 0; i < num; i++) {
            for (int j = i + 1; j < num; j++) {
                if (ver[i].size() > ver[j].size()) swap(ver[i], ver[j]);
            }
        }
        printf("%d\n", num);
        for (int i = 0; i < num; i++) {
            int sz = ver[i].size();
            printf("%d ", sz);
            for (int j = 0; j < sz; j++)
                printf("%lld%c", ver[i][j], " \n"[j == sz - 1]);
            ver[i].clear();
        }
    }
    return 0;
}

C++版本二 

#include <iostream>
#include<stdio.h>
#include <string.h>
#include<set>
#include<bits/stdc++.h>
using namespace std;
struct node
{
    long long  a,b,c,d;
};
node s[105];
void init()
{
    for(int i=0;i<105;i++)
    {
        s[i].a=-1;
        s[i].b=-1;
        s[i].c=-1;
        s[i].d=-1;
    }
}
int main()
{
    int t;
    cin>>t;
   long long  x;
 
    for(int cas=1; cas<=t; cas++)
    {
        int flag=1;
       init();
        scanf("%lld",&x);
 
        long long yu=x;
        printf("Case #%d:\n",cas);
        if((yu&(yu-1))==0)
            flag=0;
 
        for(double i=2.0; i<=68.0; i=i+1.0)
        {
            long long num=x;
            long long num1=0,num2=0;
            long long p=(long long )(pow((double)x,1.0/i));
            long long q=(long long )(pow((double)x,1.0/i))+1;
            if(p==1)
                break;
            if(q==1)
                break;
            while(num%p==0)
                num/=p,num1++;
            while(num%q==0)
                num/=q,num2++;
            if(num==1)
            {
                int k=(int)i;
                s[k].a=(num1);
                s[k].b=(p);
                s[k].c=(num2);
                s[k].d=(q);
            }
        }
        int su=0;
 
        int biaoji[1000];
        memset(biaoji,0,sizeof(biaoji));
         if(flag)
        {
 
        for(int i=0; i<105; i++)
        {
            if((s[i].a!=-1||s[i].c!=-1)&&biaoji[s[i].a+s[i].c]==0)
            {
                su++;
 
                biaoji[s[i].a+s[i].c]=1;
 
            }
        }
        }
        memset(biaoji,0,sizeof(biaoji));
        if(flag)
        {
            printf("%d\n",su+1);
         printf("1 %lld\n",(long long )x);
        for(int i=0; i<105; i++)
        {
            if((s[i].a!=-1||s[i].c!=-1)&&biaoji[s[i].a+s[i].c]==0)
            {
                printf("%lld",s[i].a+s[i].c);
                biaoji[s[i].a+s[i].c]=1;
                for(int j=0; j<s[i].a; j++)
                    printf(" %lld",s[i].b);
                for(int j=0; j<s[i].c; j++)
                    printf(" %lld",s[i].d);
                printf("\n") ;
            }
        }
        }
        else
            printf("-1\n");
    }
 
}