[BZOJ 1053][HAOI2007]反素数ant：搜索

本文主要是介绍[BZOJ 1053][HAOI2007]反素数ant：搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击这里查看原题

实际上是求n以内因数最多的数。初看数据范围会以为是数论题，实际上可以贪心，素数的次数相同时小素数比大素数更优。预处理出前若干个素数，发现前10个素数之积已超过2e9，因此可以搜索。

/*
User:Small
Language:C++
Problem No.:1053
*/
#include<bits/stdc++.h>
#define ll long long
#define inf 999999999
using namespace std;
int cnt,prime[20],sum[20];
ll ans,mx;
ll n;
bool not_prime[100];
void dfs(int now,ll num,ll sum){if(now==cnt+1){if(sum==mx) ans=min(ans,num);if(sum>mx){ans=num;mx=sum;}return;}ll tmp=1;for(int i=0;;i++){if((ll)num*tmp>n) break;dfs(now+1,num*tmp,sum*(i+1));tmp*=prime[now];}
}
int main(){freopen("data.in","r",stdin);//sum[0]=1;for(int i=2;i<100;i++){if(!not_prime[i]){prime[++cnt]=i;if((ll)sum[cnt-1]*i>=2e9) break;sum[cnt]=sum[cnt-1]*i;}for(int j=1;j<=cnt&&i*prime[j]<100;j++){not_prime[i*prime[j]]=1;if(i%prime[j]==0) break;}}scanf("%lld",&n);dfs(1,1,1);printf("%lld\n",ans);return 0;
}

这篇关于[BZOJ 1053][HAOI2007]反素数ant：搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---