历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 198. 反素数(y总字幕版，思路贼清晰) 原题链接中等

作者：

Elegant , 2021-04-13 19:41:57 , 所有人可见 , 阅读 4740

117

21

每一步操作都有y总的原话讲解哦！！思路相当清晰~~

#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;
}

码字不易，点个赞再走呗~~

32 评论

rsy_ 2022-12-11 16:10

（y总摸了摸鼻子和嘴唇继续说）
让我的脑海中立刻浮现出视频中的画面

xiuzhiyuan 2023-01-14 21:31

这种优质题解再来一打。

xiuzhiyuan 2023-01-14 21:05

联想练习器

Link_Cut_Y 2021-12-18 22:36

$好，然后…（y总摸了摸鼻子和嘴唇继续说）$

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

$好，840对吧，没问题$

再现原版$y总$

lzyz222 2022-11-22 21:43

%lcy

lihua777 2022-06-01 16:43

为什么你也可以放视频[doge]

surea 5个月前

请问佬，18的时候答案不应该是18吗，为什么代码输出的结果是12呢

yan_yu666 19天前

“你能求出不超过 N 的最大的反质数么？”

Cplusplus 2023-03-06 16:51

人才

Cplusplus 2023-03-06 09:39

@lcy

Cplusplus 2023-03-06 09:36

wocao

markding 2023-01-11 16:51

好家伙，极草

德摩斯梯尼 2022-12-08 23:39

大佬，请问一下dfs(u+1,i,p,s*(i+1))后为什么不用恢复现场

自强不息_0 10个月前

每个质因子对应的位置是固定的，下一次回溯到这一步的时候直接覆盖上一次的值

xyh2 2022-11-19 09:44

牛逼啊，哥们

道长没有道观 2022-08-29 20:16

逆天

鹤唳 2022-07-12 15:44

关于一篇题解成功唤起了我丧失已久的想象力这件事

藕丝泥霸 2022-04-15 20:11

有一个问题想请教一下大佬，为什么dfs里面for循环那里是正序循环，可不可以倒序循环，质因子次数是递减的呀

糖豆 2022-05-20 14:14

$Q$:为什么在$dfs$中循环是从小到大的，而不是从大到小的，从大到小不行吗？
$A$:也可以，但复杂的多，不推荐：

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long LL;
int ps[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
int n;

int MaxNumber; //在n以内，最大的反素数(约数个数最多)
int MaxCnt;    //取到的最大反素数MaxNumber,它有多少个约数

//快速幂模板
LL qmi(LL a, LL b) {
    LL res = 1;
    while (b) {
        if (b & 1) res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}

void dfs(int step, int last, LL number, int cnt) {
    if (step == 9) return;
    if (cnt > MaxCnt || (number < MaxNumber && cnt == MaxCnt))
        MaxNumber = number, MaxCnt = cnt;
    //如果真的要逆天而行，从大到小，那么首先需要计算ps[step]的last次方，这玩意不用快速幂就不好算
    //而且可能很大，会爆long long,需要使用ULL
    number *= qmi(ps[step], last);

    for (int i = last; i >= 1; i--) {                             //如你所愿意，倒着从大到小
        if (number <= n) dfs(step + 1, i, number, cnt * (i + 1)); //没法剪枝，只能判断不派发新任务
        number /= ps[step];                                       //由乘变除
    }
}

int main() {
    scanf("%d", &n);
    dfs(0, 30, 1, 1);
    printf("%d\n", MaxNumber);
    return 0;
}

总结