[HAOI2007]反素数ant题解

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

题目链接

分析

感觉这道题就是一道披着数论外衣的搜索
我们可以推出三个性质
1.最大反素数即为范围内因数最多的最小的那一个
2.最多有10个素因子，且素因子的幂不超过31
3.必定是最小的几个素因子相乘，且指数非严格递减
2可根据数据范围推出，最小的10个素数相乘大于2^31，所以可知。对于3，我们可根据唯一分解定理分析得出。这样搜索即可
时间：0ms。
上代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,ans1=0,ans2=0,prime[12]={0,2,3,5,7,11,13,17,19,23,29,31},num1=0,num2=0;
void dfs(ll x,ll y,ll z,ll num){if(x==num1+1){if((num>ans1))ans1=num,ans2=y;if((num==ans1)&&(ans2>y))ans2=y;return;}for(int i=0;i<=z;i++){if(y*pow(prime[x],i)>n)break;dfs(x+1,y*pow(prime[x],i),i,num*(i+1));}
}
int main(){scanf("%lld",&n);int m=n;while(m)m/=prime[++num1];m=n;while(m)m/=2,num2++;dfs(1,1,num2,1);printf("%lld\n",ans2);return 0;
}

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

---