炫酷数字 （扩展埃式筛法）

链接：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;
}