BZOJ 1053 [HAOI2007]反素数ant

质因数+搜索

显然最终答案x的质因数一定是所有质数中最小前几项，否则一定可以把较大的质因数换成一个较小的没用过的质数，而答案更优。

发现只要前十多个质数乘起来就可以超过2000000000，于是开始爆搜。

#include<cstdio> #include<cmath> #include<algorithm> using namespace std; int cnt=11, prime[12]={1,2,3,5,7,11,13,17,19,23,29,31}, ans=0, pos, n; void dfs(int now, long long num, int temp) { if(now>cnt) { if(ans<temp) { ans=temp; pos=num; } else if(ans==temp && num<pos) pos=num; return; } dfs(now+1,num,temp); for(int i = 1; num*prime[now]<=n; i++) { num*=prime[now]; dfs(now+1,num,temp*(i+1)); } } int main() { scanf("%d",&n); dfs(1,1,1); printf("%d\n",pos); return 0; }