C++(clang++11) 解法, 执行用时: 48ms, 内存消耗: 500K, 提交时间: 2021-02-01 10:14:42

#include <bits/stdc++.h>
using namespace std;
int pri[] = {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
int n, ans[100005], res[21], tmp[21];
double lg[21], mn=DBL_MAX;
void input(){
    cin>>n;
    for(int i=1; i<=16; i++) lg[i] = log(pri[i]);
}
void dfs(double x, int y, int z){
    if(x >= mn) return;
    if(y == 1){
        mn = x;
        memset(res, 0, sizeof(res));
        for(int i=1; i<=z-1;i++) res[i]=tmp[i];
        return;
    }
    if(z>16) return;
    for(int i = 0; (i+1)*(i+1)<=y; i++){
        if(y%(i+1)==0){
            if(i != 0){
                tmp[z] = i;
                dfs(x+lg[z]*i, y/(i+1), z+1);
            }
            if((i+1)*(i+1)!=y){
                tmp[z] = y/(i+1)-1;
                dfs(x+lg[z]*(y/(i+1)-1), i+1, z+1);}}}}
void work(){
    dfs(0, n, 1);
}
void output(){
    ans[0]=ans[1]=1;
    for(int i=1;i<=16;i++){
        for(;res[i]>0;res[i]--){
            for(int j=1;j<=ans[0];j++) ans[j]*=pri[i];
            for(int j=1;j<=ans[0];j++) ans[j+1]+=ans[j]/10, ans[j]%=10;
            if(ans[ans[0]+1]!=0) ans[0]++;
            while(ans[ans[0]]/10!=0){
                ans[ans[0]+1] += ans[ans[0]]/10;
                ans[ans[0]] %= 10;
                ++ans[0];
            }
        }
    }
    for(int i = ans[0]; i>=1; i--){
        printf("%d", ans[i]);
    }
}
int main(){
    input();
    work();
    output();
}

pypy3(pypy3.6.1) 解法, 执行用时: 66ms, 内存消耗: 21504K, 提交时间: 2021-03-27 22:11:37

# -*- coding: utf-8 -*-
"""
Created on Sat Mar 27 21:36:18 2021

@author: shenben
"""
from math import log
pri=[1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59]
lg=[1 for i in range(0,16+1)]
p=[0 for i in range(0,16+1)]
ans=[0 for i in range(0,16+1)]
maxx=2e9
def dfs(s:float,cur:int,k:int):
    global maxx,ans,p
    if s >= maxx:
        return
    if k==1:
        maxx=s
        ans=p[:]
        # print(ans)
        return 
    if cur > 16:
        return 
    for i in range(0,k):
        if (i+1)*(i+1) > k:
            break
        if k % (i+1) == 0:
            if i != 0:
                p[cur]=i
                dfs(s+i*lg[cur],cur+1,k//(i+1))
                p[cur]=0
            if (i+1)*(i+1) != k:
                p[cur]=k/(i+1)-1
                dfs(s+p[cur]*lg[cur],cur+1,(i+1))
                p[cur]=0
    return 

def output():
    res:int=1
    for i in range(len(ans)):
        res*=int(pri[i])**int(ans[i])
    print(int(res))
if __name__ == "__main__":
    n=int(input())
    # n=4
    for i in range(1,16+1):
        lg[i]=log(pri[i])
    dfs(0,1,n)
    output()
# def prime(n):
#     for i in range(2,n):
#         if i*i > n :
#             break
#         if n%i==0:
#             return 0
        
#     return 1
# cnt=0
# for i in range(2,100):
#     if cnt > 16 :
#         break;
#     if prime(i):
#         cnt=cnt+1
#         print(i)