\([POI2002][HAOI2007]\)反素数
题目描述
对于任何正整数x，其约数的个数记作\(g(x)\)。例如\(g(1)=1、g(6)=4\)。
如果某个正整数x满足：\(g(x)>g(i) 0<i<x\)，则称x为反质数。例如，整数\(1，2，4，6\)等都是反质数。
现在给定一个数\(N\)，你能求出不超过\(N\)的最大的反质数么？
输入输出格式
输入格式：
一个数\(N（1<=N<=2,000,000,000）\)。
输出格式：
不超过\(N\)的最大的反质数。
输入输出样例
输入样例#1：
1000
输出样例#1：
840
题解
很早就看了黄学长的博客hzwer，一直没抽出时间去写，今天有大佬留了这道题，才去补坑。
作为一个数论蒟蒻，也学了一些结论。
首先，
约数个数定理：一个数约数个数=所有（素因子的次数+1）的乘积
\[n=\prod_{i=1}^{k}p_i^{a^i}=p_1^{a^1}·p_2^{a^2}······p_k^{a^k}
\]
\]
\[g(n)=\prod_{i=1}^{k}(a_i+1)=(a_1+1)·(a_2+1)······(a_k+1)
\]
\]
\(g(n)\)即为\(n\)的约数个数。
举例说明：正整数378000共有多少个正约数？
\(378000=2^4·3^3·5^3·7^1\)，所以正约数个数为$(4+1)×(3+1)×(3+1)×(1+1)=160 $个。
以上不懂可以去问度娘 百度百科。
其次，要使小素数多才能更优（因为这样约数就多了），所以还有一个剪枝就是为了要使小素数多，指数的大小是不递增的，比如说我选\(2\)个\(2\)和\(3\)个\(3\)就不如\(3\)个\(2\)和\(2\)个\(3\)（根据约数个数定理，它们约数个数相同，但后者更小）；
我们还可以计算得一个\(2000000000\)以内的数字不会有超过\(12\)个素因子（前\(12\)个素数\(1,2,3,5,7,11,13,17,19,23,29,31\)的乘积已经超过$2000000000 $）。
然后就直接爆搜就行了。
code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
#define R register
#define P 66
using namespace std;
ll n,max_i,max_g;
int prime[P],tot,vis[P],maxdep=11;
inline void get_prime(R int n){
for(R int i=2;i<=n;i++){
if(!vis[i])
prime[++tot]=i;
for(R int j=1;j<=tot&&i*prime[j]<=n;j++){
vis[prime[j]*i]=1;
if(i%prime[j]==0)break;
}
}
}
inline void dfs(R int dep,R ll now,R ll cnt,R int last){
if(now>n)return;
if(dep==maxdep){
if(now>max_i&&cnt>max_g){
max_i=now;
max_g=cnt;
}
if(now<=max_i&&cnt>=max_g){
max_i=now;
max_g=cnt;
}
return;
}
ll tmp=1;
for(R int i=1;i<=last;i++){
dfs(dep+1,now*tmp,cnt*i,i);
tmp*=prime[dep];
if(now*tmp>n)break;
}
}
int main(){
get_prime(50);
scanf("%lld",&n);
dfs(1,1,1,20);
printf("%lld\n",max_i);
return 0;
}