引理1: 1~n中的最大反质数，就是1~n中约数个数最多的数中最小的一个(因为要严格保证g(x)>g(i))；
引理2：1~n中任何数的不同因子不会超过10个，因为他们的乘积大于2,000,000,000；
引理3: 1~n中任何数的质因子的指数总和不超过30；
引理4: x的质因子是连续的若干个最小的质数，并且指数单调递减；
对于指数的排列我们只要深搜就可以找到方案，对于不同情况判断是否更新答案；
#include <bits/stdc++.h> using namespace std; long long n; long long ans=99999999999999; int a[15]={0,2,3,5,7,11,13,17,19,23,29,31}; inline long long KSM(long long a,long long b) { long long res=1; while(b){ if(b&1) res=res*a; a=a*a; b/=2; } return res; } long long cnt=-1; inline void dfs(int dep,int now,long long sum,long long num) { if(sum>n||sum<0){ return; } if(num>cnt){ ans=sum; cnt=num; } else if(num==cnt){ if(sum<ans) ans=sum; } if(dep>10){ return; } for(register int i=now;i>=1;i--){ dfs(dep+1,i,sum*KSM(a[dep],i),num*(i+1)); } } int main() { cin>>n; dfs(1,32,1,1); cout<<ans; }
原文：https://www.cnblogs.com/kamimxr/p/11442390.html