洛谷1463 [POI2002][HAOI2007]反素数

题解 算法-搜索 数学 提高+/省选-
题目链接 编辑文章

时隔一年(差两天)来做还是不会做,甚至连我当时写的是什么都没看懂,这充分凸显了写博客的必要性

题意

求 $\le N$ 的最大数 $x$ ,满足 $\forall 1\le i\le x$ ,$i$ 的约数个数 $<$ $x$ 的约数个数。

题解

直接上搜索。先预处理可能会被用到的质数表,对于每个质数,搜索它可能会被用几次,最后如果约数个数大于当前最大值 或 约数个数相等但数值较小 都对答案进行更新。

剪枝是 因为质数是从小到大排序的,所以可以规定下一个质数的个数一定小于当前的个数。

$x$ 代表当前质数序号,$cnt$ 是约数个数,$sum$ 是当前数值,$last$ 是上次质数用的个数。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

ll n,ans,mxcnt;
ll zs[12]={0,2,3,5,7,11,13,17,19,23,29,31};

void dfs(ll x,ll cnt,ll sum,ll last)
{
    if (x==12)
    {
        if (cnt>mxcnt || (cnt==mxcnt && sum<ans))
        {
            ans=sum;
            mxcnt=cnt;
        }
        return;
    }
    ll s=1;
    for (ll i=0;i<=last;i++)
    {
        dfs(x+1,cnt*(i+1),sum*s,i);
        s*=zs[x];
        if (sum*s>n) break;
    }
}

int main()
{
    scanf("%lld",&n);
    dfs(1,1,1,12);
    return !printf("%lld",ans);
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空