CF27E Number With The Given Amount Of Divisors 题解
简要题意：
求最小的有 (n) 个因数的数 (s)。(n leq 10^3) ,保证 (s leq 10^{18}).
考虑质因数分解：
[s = prod_{i=1}^k p_i^{a_i}
]
(p_i) 为质数。那么 (s) 的因数个数就会是
[prod_{i=1}^k (a_i + 1)
]
考虑最大的 (p_i) 会是几呢？
(2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 47 = 614889782588491410)，约为 (6.1 imes 10^{17})，所以 (p_i) 最大为 (53).
考虑搜索从大到小枚举当前 (p_i) 的指数，并计算当前的因数个数与 (s).
具体代码具体分析：
inline void dfs(ll dep,ll temp,ll num,ll last) {
//dep 是当前搜索的素数编号 , temp 是当前的数 , num 是 temp 的因数个数 , last 表示当前最大的指数
if(num>n || dep>16) return; //超出范围
if(num==n && ans>temp) {
ans=temp; return; //更新答案
} for(int i=1;i<=last;i++) {
if(temp/p[dep]>ans) break; //最优性剪枝
dfs(dep+1,temp=temp*p[dep],num*(i+1),i); //往下走一层
}
}
(p) 是提前打好的素数表，只需要打 (16) 个。
dfs(0,1,1,64);
最后输出 ( ext{ans}) 即可得到答案。
时间复杂度：(mathcal{O}( ext{wys})).
实际得分：(100pts).
细节：
你可能需要 ( ext{unsigned long long})，因为答案溢出最大可以到 temp * p[dep]，( ext{long long}) 应该不能过。
#include<bits/stdc++.h>
using namespace std;
inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0;while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;}
typedef unsigned long long ll;
#define INF ~0LL
ll p[16]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
ll n,ans;
inline void dfs(ll dep,ll temp,ll num,ll last) {
if(num>n || dep>16) return;
if(num==n && ans>temp) {
ans=temp; return;
} for(int i=1;i<=last;i++) {
if(temp/p[dep]>ans) break;
dfs(dep+1,temp=temp*p[dep],num*(i+1),i);
}
}
int main(){
ans=INF;
n=read();
dfs(0,1,1,64);
printf("%llu
",ans);
return 0;
}