---
title: "反素数"
created: 2025-11-28
tags:
  - 算法
---

# 反素数

## 题目 [反素数](https://www.acwing.com/problem/content/200/)

![[image-4bd6550e.png]]

## 思路分析

分析题意的时候 看着打的表有点想用刚才刚整理的倍增思想的冲动 就试了一下 好像可以

![[image-6fb3e5ee.png]]

从1做到n 把每个数的倍数的记录数都++（实际含义是 这些数都包含这个因子）

结束后 g[i]记录的就是每个数的约数的数量 然后就是找一个单调递增的顶峰

贪心想一下 好像可以直接找最大值 如果它最大 就一定比左边的所有的都大 对于左边来说它一定是答案 对于右边来说 右边某个数的左边是这个最大值
那么一定不是单增 那右边一定没有答案 好像是可以的

那就用一个max维护就好了

```cpp
const int N=2e9+10;

int g[N];

//开不了 太大了 开到1e6+10能过6个

//改成vector版本

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

int main()

{

    int n;

    cin>>n;

    vector<LL> g(n);

    for(int i=1;i<=n;i++){

        for(int j=i;j<=n;j+=i){

            g[j]++;

        }

    }

    int maxv=-1,idx=1;

    for(int i=1;i<=n;i++){

        if(g[i]>maxv){

            maxv=g[i];

            idx=i;

        }

    }

    cout<<idx;

    return 0;

}
```

报错

terminate called after throwing an instance of '`std::bad_alloc' what(): std::bad_alloc`

`std::bad_alloc`异常通常发生在内存分配失败时 当 n 达到 $2×10^9$ 时，你正在尝试分配超过
16GB 的内存，这超出了大多数系统的能力。

不过没关系 大胆尝试下 60分还是可以接受的

![[image-4fbf2446.png]]

最近养成了一个习惯 拿到题先自己写一下 虽然知道可能不能ac 但是没关系 这也熟悉了题型 还巩固了已有知识 并且锻炼了暴力的能力 因为比赛时其实更多的都是先写暴力
再在基础上思考改进 除非是已经见过的知识点 才可能跳过这个暴力的步骤 那现在其实就是处于一个 温故且知新的阶段 在不断练习巩固应用已有知识下
同时又学到新的技巧 把它化为己用 下次再遇到 那就是又是已有知识库里的东西了

好了 来看一下其他人怎么写 应该又有一个什么没见过的技巧

这个问题是关于寻找不超过给定数 N )的最大反素数。在数论中，反素数是具有更多约数的数相对于它的大小而言。也就是说，在小于等于它的所有数中，没有任何数有比它更多的约数。问题的关键是如何有效地找到满足这个性质的数。

这里采取的是一种基于深度优先搜索（DFS）的递归方法。思路是枚举所有可能的由质因数构成的乘积，并找出满足条件的数。这种方法是建立在以下性质之上：

1. 在小于等于 N 的所有数中，如果有多个数约数个数相同，反素数是这些数中最小的那个。这是因为如果有两个数 a 和 b ，且它们的约数个数相同，但
   a < b，则 b 不能是反素数，因为存在比它小的数 a 具有相同数量的约数。
2. 在 1 到$ 2 \* 10^9 $的范围内，能够成为反素数质因子的最大数是
   23 ，因为超过这个数的质数的乘积会超过 $2 \* 10^9$ 。
3. 对于每个质数，其指数（在反素数质因数分解中的次数）是有上限的。例如，对于 2 ，其指数不会超过 30 ，因为 $2^{31}$会超过
   $2 \* 10^9$。
4. 质因子的指数应该是递减的。也就是说，如果 2 的指数是 i ，那么 3 的指数不会超过 i 。这是基于如果存在两个质因数 p 和 q ，且
   p < q 但 p 的指数小于 q 的指数，那么我们可以通过增加 p 的指数来获得一个更小的数，该数的约数个数至少与当前数一样多。

代码实现了上述思路，其中 `dfs` 函数是关键。它递归地尝试所有可能的质因数和它们的指数，并且跟踪约数的最大数量以及对应的最小数。这是通过以下参数控制的：

- `u`: 当前正在枚举的质数索引。
- `last`: 可以使用的最大指数。
- `num`: 当前的乘积（可能的反素数）。
- `sum`: 当前乘积的约数数量。

如果当前的约数数量超过了之前找到的最大数量，或者约数数量相同但数更小，则更新最大约数数量和最小数。

在 `main` 函数中，程序开始了递归过程，并在最后输出找到的最大反素数。这种方法利用了数论的深刻性质，并通过深度优先搜索找到了最优解。在计算过程中，该算法确保了乘积不会超过
( N )，从而避免了不必要的搜索，并保持了算法的效率。

？这是人想得出来的？ 首先能枚举到23都不可能想得到

前面的当我没说 这种技巧学不来

## 代码实现

```cpp
#include<iostream>

#include<cstring>

// #include<cstdio>由于这个题目的读入量很小，所以我们完全可以用cin来读

#include<algorithm>

using namespace std;

int primes[9]={2,3,5,7,11,13,17,19,23};//primes的话一共是有9个对吧

typedef long long LL;//当然这里要加一个long long 啊

int maxd;//比方说我们的约数个数可以记为我们的maxd

int number;//然后数本身的话可以记成number

int n;//然后还有一个n对吧，这是我们读入的这个数

void dfs(int u,int last,int p,int s)//好，那我们dfs一下,上一个的次数，上一个数，以及我们的约数个数

{

    //好，然后如果我们当前的约数个数是大于我们的最大约数个数了

    //或者是等于等于最大约数个数并且p小于number的话

    if(s>maxd||s==maxd&&p<number)

    {

        maxd=s;//我们就要更新一下

        number=p;//然后number等于p，对吧

    }

    //好，接下来的话就去枚举一下啊

    //当然这里我们要判断一下啊，如果u已经的等于9了，表示已经枚举了所有情况了，那么我们就可以直接return了

    if(u==9)return;

    //然后接下来去枚举一下次数

    //次数的话咱们从一次开始枚举，一直枚举到第，last次对吧，不能比上一次多

    for(int i=1;i<=last;i++)

    {

        if((LL)p*primes[u]>n)//那每次都先算一下我们这个这个，p乘上一个我们当前的质数，看一下是不是已经大于n了

        break;//大于n的话那就直接break就可以了对吧

        //好，然后否则的的话，咱们就让p就乘上一个primes[u]

        p*=primes[u];

        //好然后再dfs下一次

        dfs(u+1,i,p,s*(i+1));//u+1,然后是这个i，对吧，p,还有这个s*(i+1);

        //好，然后我们来调试一下

    }

}

int main()

{

    cin>>n;

    /*字            幕        开          始*/

    //首先dfs一遍

    //那么dfs里面是有几个参数呢？

    //第一个是我们枚举到第几个质数了，第0个对吧，从第0个开始枚举

    //然后下一个的话是我们的次数最大是多少对吧，那我们刚刚说了次数最大是30对吧，当前最大次数是30

    //然后我们这个数本身乘积是多少？这个乘积本身是1对吧

    //好，然后...（y总摸了摸鼻子和嘴唇继续说）呃...下一个，下一个应该是约数个数对吧，约数个数的话最开始是1对吧

    //因为我们约数个数是通过公式来算的，每次都要乘上一个数，所以在没乘之前应该是1

    dfs(0,30,1,1);

    //哦，忘记输出了咱们，咱们要把这个答案输出

    cout<<number<<endl;

    //好，840对吧，没问题

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[倍数思想|倍数思想]] 🏠 [[00-刷题理模型]] ➡️ [[基础约数|基础约数]]