链接:https://ac.nowcoder.com/acm/contest/331/G
来源:牛客网
时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 131072K,其他语言262144K
64bit IO Format: %lld
题目描述
小希希望你构造一个最小的正整数,使得其有n个因子。
输入描述:
第一行一个整数T表示数据组数 每组数据第一行输入一个正整数n,表示其因子数。 n≤1,000,000 T≤1,000,000
输出描述:
输出一行一个整数,表示你构造出的这个数。注意:你需要保证你构造的数≤1,000,000,如果在这个范围里面无法构造出一个正整数满足条件,请输出-1。
示例1
输入
2 4 5
输出
6 16
题意:找到有n个因子的最小值。单来说就是:找一个数的因子的个数。
题解:预处理一下,处理处所有因子数的最小值,下标代表因子数,值代表最小值~~详细看代码:
#include <iostream>
#include <cstdio>
using namespace std;
const int MAX = 1e6+520;
int a[MAX],b[MAX];
void init(){//扩展埃式筛法
for (int i = 1; i <= 1e6;i++){
for (int j = i; j <= 1e6;j+=i){
a[j]++;
}
if(!b[a[i]]){//保证是最小的
b[a[i]]=i;//下标保存因子数,值对应的最小值
}
}
}
int main(){
init();
int t;
scanf("%d",&t);//要用标准输入输出,要不然超时哦~~
while(t--){
int n;
scanf("%d",&n);
if(b[n]==0) printf("-1\n");
else printf("%d\n",b[n]);
}
return 0;
}