【BZOJ1053】[HAOI2007]反素数 (搜索+数论)

时间:2024-10-15 15:04:08

\([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;
}