CF27E

Number With The Given Amount Of Divisors

根据一些反素数的结论，这题就可以直接上爆搜了。

对于含有 $n$ 个正因子的最小数 $x = \prod _ { i = 1 } ^ { k } p _ i ^ { c _ i }$，一定满足：

• $p_1 = 2$。
• 质数是连续的。
• $c _ { i + 1 } \le c _ i$。

搜就完了。

时间复杂度玄学。

开了 __int128，CF 上要 C++20 才能正确提交。。。

反过来如果要求 $n$ 以内因子最多的。。。反过来搜不就完了。。。

反素数不爆搜还能干什么？

代码：

#include<iostream>
#include<cstdio>
#define ll __int128
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;

ll n,ans=1e18+1;
ll prime[20]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};

inline void Dfs(ll x,ll step,ll lst,ll cnt) {
  if(cnt>n) return;if(x>ans) return;if(step>16) return;
  if(cnt==n) {ans=min(ans,x);return;}
  ll tmp=x;
  for(ll i=1;i<=lst;i++) {
    tmp*=prime[step];Dfs(tmp,step+1,i,cnt*(i+1));
  }
}

int main() {

  n=read();

  Dfs(1,0,64,1);

  write(ans);

  return 0;
}