题目描述
给定 N
,求非严格小于(小于等于) $N$ 的最大反素数。
反素数定义:
定义 g[i] 表示一个数约数个数,如果一个 x,满足所有严格小于 x 的 i ,都有 g[i] < g[x],称 x 是反素数
。
简单说,就是希望这个数约数个数比所有比自己小的数的约数个数都多。
数据范围: $N\le 2\times 10^9$
样例
1000
算法1 打表
$O(\log n)$
如果你实在没有思路,那么不妨试试暴力骗分,也许在暴力骗分的过程中,就发现了正解。
发现 N
很大,考虑拿部分分,用一个暴力算法跑出反素数表,每次询问的时候在表里 lower_bound
一下小于等于自己的反素数即可。
打表代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e8+8;
int maxsig=1;
signed main(){
printf("1\n");
for(int i=2;i<=maxn;i++){
int cnt=0;
for(int j=1;j<=i/j;j++){
if(i%j==0)cnt+=2;
}
if(cnt>maxsig){
maxsig=cnt;
printf("%d\n",i);
}
}
}
打着打着表,突然发现没有想象中,$2\times 10^9$ 那么多啊?
通过 打表, 数学直觉,我们敏锐的感觉到反素数的分布,应该是间距很大的
事实上 10000 以下只有 20 个反素数,同时随着数字变大,约数之和越来越大,反素数越来间距越大
那存储倒是没什么问题了,我完全可以开数组存下来,可是这跑 $2e9$ 太慢了啊,时间复杂度太难以接受了。
其实你可以用复杂度更低一些的算法,如果空间复杂度过高,可以使用一个偏移量,分段打表,最后放一块即可。
不过这里还是有其他方法,你打出来部分表就会发现
1,2,4,6,12,24,36,48,60,120,180,240,360,720,840
这差值…有点意思啊。
那我们就考虑记录下差值,大胆猜测,未来的反素数只会是原来的反素数加某个位置差值的倍数,大大优化了时间复杂度。
具体打表代码,因为我没写,这里放一个链接,可以在这篇博客上查看。
我直接用 OEIS
,把打出来的比较小的数扔了上去,查出来了这个数列。
,具体文献在 Link。
那么代码就比较显然了。
#include <bits/stdc++.h>
using namespace std;
int reprime[70]=
{1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,
25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,554400,665280,
720720,1081080,1441440,2162160,2882880,3603600,4324320,6486480,7207200,8648640,10810800,
14414400,17297280,21621600,32432400,36756720,43243200,61261200,73513440,110270160,122522400,
147026880,183783600,245044800,294053760,367567200,551350800,698377680,735134400,1102701600,
1396755360,2095133040};
signed main(){
int n;
cin>>n;
int t=lower_bound(reprime,reprime+70,n)-reprime;
printf("%d\n",reprime[--t]);//这里似乎如果N恰好是反素数会错,估计是数据水
//各位如果用打表应当特判一下N恰好是反素数的情况
}
算法2
搜索
时间复杂度不明,反正带剪枝的搜索往往是 $\mathcal{O}(玄学)$以及$\mathcal{O}(能过)$ 级别的。
这需要你注意到这么几个问题:
考虑一个问题,如果一个数是反素数,它一定是质因子尽量多,次数尽量高,因数个数才会尽量大。
1. 考虑最多几个质因子,你会发现最多连乘到 23 就超过 2e9 了,也就是最多也就 9 个
2. 再考虑次数,你发现最大 2^31 次方也就超过了。
3. 又发现发现,一个反素数的质因数次数一定是递减的,否则假设存在某个位置递增,我们交换指数,就会发现新的数比它小,而且约数个数和他一样,不符合反素数严格大于的定义。
综上,我们发现其实约数就那么几个,次数就那么点,递减作为剪枝,能过。
那么大力搜索即可,搜索时,因为需要递减剪枝,记录上一个选了几个,因为需要知道约数个数,所以记录下来,因为需要知道反素数是否会大于所求范围,所以记录大小,因为需要知道你要填什么数,所以记录填到第几个素数。
综上,需要记录:
1. 此时的约数个数
2. 此时数的值
3. 目前是第一个约数
4. 上一个次数是多少
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int prime[]={2,3,5,7,11,13,17,19,23};//提前处理一下能取的prime
int reprime=0,resig=0;
void dfs(int x,int idx,int sum,int sig){//第几位 位数 值 约数个数
if(sig>resig || sig==resig && sum<reprime){
//比原来的更优,要么约数个数更多,要么约数个数一样,但是比原来的小,就说明原来的并非反素数
reprime=sum,resig=sig;//update
}
if(x==9)return;//搜完了,走人
ll base=prime[x];//搞一搞
for(int i=1;i<=idx;i++,base*=prime[x]){//这一位约数选几个?
if((ll)sum*base>n)break;//如果超过范围就算了吧
// if((ll)sum*prime[x]>n)break;
// sum*=prime[x];
dfs(x+1,i,sum*base,sig*(i+1));//传正确参数,往下搜
}
}
int main(){
cin>>n;
dfs(0,30,1,1);//搜
printf("%d\n",reprime);//反素数
return 0;
}