洛谷 P1463、POI2002、HAOI2007 反素数

题意：

求最小的$x\in[1,N]$，使得$x$为$g(x)$最大的数中最小的一个。

分析：

1.$x$不会有超过$10$个不同质因子。理由：$2 \times 3\times 5...\times 31>2\times 1e9$
$2\times 3\times 5...\times 29<2\times 1e9$。
$2$至$29$质数刚好$10$个。

2.质因子指数不会大于$30$。理由：当取最小的质因子$2$时，$231>2\times 1e9$，$230<2\times 1e9$。

3.若$x=p_1^{c_1}p_2^{c_2}...p_n^{c_n}$，则x的因子个数为$(c_1+1)(c_2+1)...(c_n+1)$。即：$g(x)=(c_1+1)(c_2+1)...(c_n+1)$。

4.质因子连续、指数不升。理由：反证法。若$x=p_1^{c_1}p_2^{c_2}...p_n^{c_n}$，且存在$p_{n-1}<p'<p_n$，则

$x_0=p_1^{c_1}p_2^{c_2}...p_{n-1}^{c_{n-1}}p'^c_n<x$
，$g(x_0)=g(x)$，不符合题意。

若存在$c_n>c_{n-1}$，则将$c_n$，$c_{n-1}$位置交换，也不符合题意

综上所述，可以用上述几个约束条件进行搜索剪枝。

代码就是简单的$DFS$。

#include<iostream>

#include<vector>

typedef long long ll;

using namespace std;

const ll pa[]={,,,,,,,,,,};

ll n,ans=,g=;

void dfs(ll p,ll t,ll now,ll ng)

{

    if(now>n) return;

    if(p>) return;

    ll temp=ng;

    for(ll i=;i<=t;i++){

        now*=pa[p];

        ng=temp*(i+);

        if(now>n) return;

        if(ng>g) ans=now,g=ng;

        if(ng==g) ans=min(now,ans);

        dfs(p+,i,now,ng);

    }

}

signed main()

{

    cin>>n;

    dfs(,,,);

    cout<<ans;

    return ;

}

巴特西

洛谷 P1463、POI2002、HAOI2007 反素数

题意：

分析：

最新文章

热门文章