反素数
题目 反素数
思路分析
分析题意的时候 看着打的表有点想用刚才刚整理的倍增思想的冲动 就试了一下 好像可以
从1做到n 把每个数的倍数的记录数都++（实际含义是 这些数都包含这个因子）
结束后 g[i]记录的就是每个数的约数的数量 然后就是找一个单调递增的顶峰
贪心想一下 好像可以直接找最大值 如果它最大 就一定比左边的所有的都大 对于左边来说它一定是答案 对于右边来说 右边某个数的左边是这个最大值 那么一定不是单增 那右边一定没有答案 好像是可以的
那就用一个max维护就好了
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分还是可以接受的
最近养成了一个习惯 拿到题先自己写一下 虽然知道可能不能ac 但是没关系 这也熟悉了题型 还巩固了已有知识 并且锻炼了暴力的能力 因为比赛时其实更多的都是先写暴力 再在基础上思考改进 除非是已经见过的知识点 才可能跳过这个暴力的步骤 那现在其实就是处于一个 温故且知新的阶段 在不断练习巩固应用已有知识下 同时又学到新的技巧 把它化为己用 下次再遇到 那就是又是已有知识库里的东西了
好了 来看一下其他人怎么写 应该又有一个什么没见过的技巧
这个问题是关于寻找不超过给定数 N )的最大反素数。在数论中，反素数是具有更多约数的数相对于它的大小而言。也就是说，在小于等于它的所有数中，没有任何数有比它更多的约数。问题的关键是如何有效地找到满足这个性质的数。
这里采取的是一种基于深度优先搜索（DFS）的递归方法。思路是枚举所有可能的由质因数构成的乘积，并找出满足条件的数。这种方法是建立在以下性质之上：
- 在小于等于 N 的所有数中，如果有多个数约数个数相同，反素数是这些数中最小的那个。这是因为如果有两个数 a 和 b ，且它们的约数个数相同，但 a < b，则 b 不能是反素数，因为存在比它小的数 a 具有相同数量的约数。
- 在 1 到$ 2 * 10^9 $的范围内，能够成为反素数质因子的最大数是 23 ，因为超过这个数的质数的乘积会超过 \(2 * 10^9\) 。
- 对于每个质数，其指数（在反素数质因数分解中的次数）是有上限的。例如，对于 2 ，其指数不会超过 30 ，因为 \(2^{31}\)会超过 \(2 * 10^9\)。
- 质因子的指数应该是递减的。也就是说，如果 2 的指数是 i ，那么 3 的指数不会超过 i 。这是基于如果存在两个质因数 p 和 q ，且 p < q 但 p 的指数小于 q 的指数，那么我们可以通过增加 p 的指数来获得一个更小的数，该数的约数个数至少与当前数一样多。
代码实现了上述思路，其中 dfs 函数是关键。它递归地尝试所有可能的质因数和它们的指数，并且跟踪约数的最大数量以及对应的最小数。这是通过以下参数控制的：
u: 当前正在枚举的质数索引。last: 可以使用的最大指数。num: 当前的乘积（可能的反素数）。sum: 当前乘积的约数数量。
如果当前的约数数量超过了之前找到的最大数量，或者约数数量相同但数更小，则更新最大约数数量和最小数。
在 main 函数中，程序开始了递归过程，并在最后输出找到的最大反素数。这种方法利用了数论的深刻性质，并通过深度优先搜索找到了最优解。在计算过程中，该算法确保了乘积不会超过
( N )，从而避免了不必要的搜索，并保持了算法的效率。
？这是人想得出来的？ 首先能枚举到23都不可能想得到
前面的当我没说 这种技巧学不来
代码实现
#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;
}
💬 评论