题干：
“我不做人啦，jojo！”
“Dillonh起来回答问题！”
“啊？”沉迷于jojo的Dillonh又一次上课摸鱼被老师抓到了，他慌忙地抬起头看着讲台上火冒三丈的老师。
“给你一个数n，现在要找到一个集合AA,AA中若干数a1,a2,……ama1,a2,……am，使得n=a1∗a2∗a3∗……∗amn=a1∗a2∗a3∗……∗am，同时对于任意的i和j（1≤i,j≤n1≤i,j≤n）都要满足∣∣ai−aj∣∣≤1|ai−aj|≤1，你能找到所有满足这个条件的集合AA吗。如果对于这个数n有无限多个可能的集合AA，那么就输出-1，否则就输出所有不同的集合。”如果眼神能杀人的话，此刻的Dillonh就已经被他的老师杀了千万遍了。
“这...”沉迷摸鱼的Dillonh自然是不会做这个题的，他现在急的满头大汗。作为聪明的ACMer,你能帮他解决这个问题吗？
（对于两个集合AA和BB，如果两个集合内元素的个数不同的话，就认为这两个集合是不同的；如果这两个集合内元素个数相同的话，如果两个集合内的元素不论以任何顺序排序之后，仍然是不完全相同的话，那么就认为这两个集合是不同的）。
输入描述:
第一行一个数字T，代表有T组测试样例（T<=100）
对于每组测试样例都会输入一个数字n，代表老师提出的问题的数。（n≤1018n≤1018）。
输出描述:
对于每组测试样例，第一行输出一个“Case #x:”，x代表当前为第几组测试样例。
如果有无限多个满足条件的集合，第二行就输出“-1”；
否则的话，第二行输出一个数字m，代表有m个集合是满足条件的。
接下来m行输出这m个集合的信息，按集合内元素个数的大小从小到大输出，
每行的第一个数num代表集合内元素的个数，接下来按从小到大输出num个数。每行的两个数之间用一个空格隔开，行末不要有空格。 示例1
输入
2
12
1 输出
Case #1:
3
1 12
2 3 4
3 2 2 3
Case #2:
-1 解题报告：
（来自官方题解）
这是一个考验数学思维的题目。
当满足条件的集合内只有两个数的时候，要么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相乘的形式，故有无数个集合。最后再按要求处理一下输出就可以了。
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
const ll mod = 1e9+7;
typedef long double ld;
int T;
ll n;
vector<vector<ll> > vv;
int main() {
scanf("%d",&T);
int cas=1;
while(T--) {
scanf("%lld",&n);
ll x=n;
while(x%2==0)x/=2;
printf("Case #%d:\n",cas++);
if(x==1)printf("-1\n");
else {
vv.clear();
for(int i=1; i<=60; i++) {
ll t=(ll)powl((ld)n,(ld)(1.0/i));
if(t==1)continue;
x=n;
vector<ll> v;
while(x%t==0)x/=t,v.push_back(t);
while(x%(t+1)==0)x/=t+1,v.push_back(t+1);
if(v.size()==i&&x==1)vv.push_back(v);
}
printf("%d\n",vv.size());
int up = vv.size();
for(int i = 0; i<up; i++) {
printf("%d",vv[i].size());
int upp = vv[i].size();
for(int j = 0; j<upp; j++) printf(" %lld",vv[i][j]);
printf("\n");
}
}
}
return 0;
} 总结：注意精度问题所以需要powl函数
京公网安备 11010502036488号