CSDN同步
原题链接
简要题意：
求最小的有 \(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 \times 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);
最后输出 \(\text{ans}\) 即可得到答案。
时间复杂度：\(\mathcal{O}(\text{wys})\).
实际得分：\(100pts\).
细节：
你可能需要 \(\text{unsigned long long}\)，因为答案溢出最大可以到 temp * p[dep]，\(\text{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\n",ans);
return 0;
}
