C++11(clang++ 3.9) 解法, 执行用时: 1536ms, 内存消耗: 620K, 提交时间: 2019-01-30 14:26:56

#include<bits/stdc++.h>
using namespace std;
int t,ge,l[10010],a,b;
long long n,o[10010][100],u,v;

int main(){
	scanf("%d",&t);
	for(int i=1;i<=t;i++){
		printf("Case #%d:\n",i);
		scanf("%lld",&n);
		u=n;
		while(u%2==0) u/=2;
		if(u==1){
			printf("-1\n");
			continue;
		}
		l[1]=ge=1;
		o[1][l[1]]=n;
		v=u=floor(sqrt(n));
		if(u*u==n) l[++ge]=2,o[ge][1]=u,o[ge][2]=u;
		if(u*(u+1)==n) l[++ge]=2,o[ge][1]=u,o[ge][2]=u+1;
		for(long long k=1000000;k>=2;k--){
			if(k==v||k==n) continue;
			u=n,a=0,b=0;
			if(u%k==0){
				while(u%k==0) u/=k,a++;
				while(u%(k+1)==0) u/=(k+1),b++;
				if(u==1){
					l[++ge]=a+b;
					for(int i=1;i<=a;i++) o[ge][i]=k;
					for(int i=1;i<=b;i++) o[ge][a+i]=k+1;
				}
			}
		}
		printf("%d\n",ge);
		for(int i=1;i<=ge;i++){
			printf("%d",l[i]);
			for(int j=1;j<=l[i];j++){
				printf(" %lld",o[i][j]);
			}
			printf("\n");
		}
	}
	
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 12ms, 内存消耗: 628K, 提交时间: 2018-12-29 22:51:17

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
vector<vector<LL>>ans;
vector<LL>v;
int main()
{
	int T;
	cin>>T;
	LL n;
	int cas=1;
	LL x;
	int i;
	while(T--)
	{
		cin>>n;
		x=n;
		while((x&1)==0)
			x>>=1;
		cout<<"Case #"<<cas++<<":"<<endl;
		if(x==1)
		{
			printf("-1\n");
			continue;
		}
		for(i=1;i<=63;i++)
		{
			LL t=powl(n,1.0/i);
			if(t<=1)
				continue;
			x=n;
			v.clear();
			while(x%t==0)
			{
				v.push_back(t);
				x/=t;
			}
			while(x%(t+1)==0)
			{
				v.push_back(t+1);
				x/=t+1;
			}
			if(x==1&&v.size()==i)
				ans.push_back(v);
		}
		cout<<ans.size()<<endl;
		for(const auto&x:ans)
		{
			cout<<x.size();
			for(const auto&y:x)
				cout<<' '<<y;
			cout<<endl;
		} 
		ans.clear(); 
	}
	return 0;
}