我一开始以为有什么很牛逼的方法来做，然后一直没有思路
后来看了https://blog.csdn.net/zju2016/article/details/78562932的博客
竟然是暴搜？？？？？？？？？？？/
好我服了
大致思路：素数的范围在100以内
因为要求尽量小，所以素数取得要尽量小
在100内的素数有20多个，这20多个配合上幂
是可以凑到2的63次方那么大的
那么我们枚举素数，得出的组合个数再与题目给的比较
然后这里有个贪心，因为要尽量小，所以素数小的要取多一些
大的取小一些，所以素数幂应该随着素数增大越来越小
然后有个比较难理解的是给一个数字怎么算组合个数
假设p = a1^k1 * a2^k2 ……ak ^ kr
其实就是算有重复元素的全排列
可以理解为有k1个a， k2个b， k3个c ……
然后求全排列
那么我们设一共有n个元素，即k1 + k2 ……kr = n
那么假设最终答案为x
那么x * k1! * k2! ……kr! = n!
也就是说如果不看重复，总的排列数为n的阶乘
那么如果看重复就是x种，而每一种里面每一块
重复的元素都可以做一个小的全排列。
例如k1个a， 就有k1 !个方案
根据乘法原理，x * k1! * k2!……kr! 所得出的也是不看重复下全排列的个数
所以移项可以得x = n! /( k1 ! * k2!……kr!)
讲这个干嘛呢？
主要是为了解释加入了新元素组合总数会有什么变化
设在原来的基础上新加入了k个相同的元素
那么 新的方案x1 = （n+k）! /( k1 ! * k2!……kr! * k!)
那么我们用x1/x，可以算出
x1 / x = (n+k)! / (n!*k!)
看到(n+k)! / (n!*k!)你想到了什么？？？？？
非常巧的是，这就是c(n+k, k)
所以我们可以预处理组合数。
#include<cstdio>
#include<cstring>
#include<vector>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
typedef unsigned long long ull;
const int MAXN = 112;
ull c[MAXN][MAXN], n;
bool is_prime[MAXN];
vector<int> prime;
void init()
{
memset(is_prime, true, sizeof(is_prime)); //线性筛法
is_prime[0] = is_prime[1] = false;
REP(i, 2, MAXN)
{
if(is_prime[i]) prime.push_back(i);
REP(j, 0, prime.size())
{
if(i * prime[j] >= MAXN) break;
is_prime[i * prime[j]] = false;
if(i % prime[j] == 0) break;
}
}
REP(i, 0, MAXN) //推组合数
{
c[i][0] = c[i][i] = 1;
REP(j, 1, i) c[i][j] = c[i-1][j-1] + c[i-1][j];
}
}
void dfs(ull k, ull& ans, ull now, int ind, int pre, int up) //pre就是幂的总数，ind是当前应该从哪个素数开始用
{ //up是为了保证小的素数取得多，这样更优
if(k > ans || ind > prime.size() || now > n) return; //超级无敌剪枝
if(now == n) { ans = k; return; }
ull t = 1;
REP(i, 1, up + 1) //枚举当前这个素数的幂
{
t *= prime[ind];
if(k > ans / t) return; //这么写防止溢出
dfs(k * t, ans, now * c[pre+i][i], ind + 1, pre + i, i); //注意这里now的更新，解析中推过了
}
}
int main()
{
init();
while(~scanf("%llu", &n))
{
if(n == 1) { puts("1 2"); continue; } //我觉得2不能分解成素数乘积，组合的个数应该是0
ull ans = 1ULL << 63; //但是题目样例是这么给的，那么就特判吧。
dfs(1, ans, 1, 0, 0, 63);
printf("%llu %llu
", n, ans);
}
return 0;
}