题意:求小于n的约数最多的正整数.
由唯一分解定理得一个数$ x=p_1^{a_1}p_2^{a_2}...p_n^{a_n}(p_1<p_2<.....<p_n) $
则他的约数个数为$ (a_1+1)(a_2+1)...(a_n+1). $
若x是反素数,则 $a_1>=a_2>=a_3.....>=a_n$,随便调换两个数的位置得到的都是更差的解.
这样的话降序搜索就行了.且质因子最多为10个.
时间复杂度我不会证QWQ
#include<bits/stdc++.h> using namespace std; typedef long long LL; LL n,ans,maxx=0; LL a[20]={0,2,3,5,7,11,13,17,19,23,29}; void dfs(int id,int p,LL x,LL y){ if(y>maxx){ maxx=y; ans=x;} if(y==maxx&&ans>x) ans=x; if(id==11) return; LL tmp=1; for(int i=1;i<=p;++i){ tmp*=a[id]; if(x*tmp>n) break; dfs(id+1,i,x*tmp,y*(i+1)); } } int main(){ scanf("%lld",&n); dfs(1,31,1,1); printf("%lld\n",ans); cout<<maxx<<endl; return 0; }
原文：https://www.cnblogs.com/huihao/p/11746334.html