题解 P1463 [POI2002][HAOI2007]反素数

· · 题解

题意：

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

分析：

1.x不会有超过10个不同质因子。

2 \times 3\times 5...\times 31>2\times 10^9 $2$至$29$质数刚好$10$个。 2.质因子指数不会大于$30$。理由：当取最小的质因子$2$时，$231>2\times 1e9$，$230<2\times 10^9$。 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)，不符合题意。

5.指数不升

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

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

代码就是简单的DFS。

#include<iostream>
#include<vector>
typedef long long ll;
using namespace std;
const ll pa[16]={0,2,3,5,7,11,13,17,19,23,29};
ll n,ans=1,g=0;

void dfs(ll p,ll t,ll now,ll ng)
{
    if(now>n) return;
    if(p>10) return;
    ll temp=ng;
    for(ll i=1;i<=t;i++){
        now*=pa[p];
        ng=temp*(i+1);
        if(now>n) return;
        if(ng>g) ans=now,g=ng;
        if(ng==g) ans=min(now,ans);
        dfs(p+1,i,now,ng);
    }
}

signed main()
{
    cin>>n;
    dfs(1,30,1,1);
    cout<<ans;
    return 0;
}

//

19-3-24

修改了部分L^AT_EX