填坑

Problem

对于任何正整数 x，其约数的个数记作 g(x)。例如 g(1)=1、g(6)=4。

如果某个正整数 x 满足：g(x)>g(i) 0<i<x，则称 x 为反质数。例如，整数 1，2，4，6 等都是反质数。

现在给定一个数 N，你能求出不超过 N 的最大的反质数么？

Solution

找因子个数最大的最小数
贪心得到的限制条件：分解质因数指数递减
爆搜即可

Code

// Code by ajcxsu
// Problem: dprime

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

typedef int __int;
#define int long long
const int N=1000, OP=31;
int pri[N], p;
char npri[N];
int ph[OP][OP];

int pl1, pl2;
int n;
void dfs(int x, int st, int pl, int su) {
    if(su>n) return;
    if(pl>pl1 || (pl==pl1 && su<pl2)) pl1=pl, pl2=su;
    if(x==p) return;
    for(int i=st;i>=0;i--) if(ph[x][i] && ph[x][i]*su>0)
        dfs(x+1, i, pl*(i+1), su*ph[x][i]);
}

__int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin>>n;
    npri[1]=1;
    for(int i=2;i<N && p<OP;i++) {
        if(!npri[i]) pri[p++]=i;
        for(int j=0;j<p && i*pri[j]<N;j++) {
            npri[i*pri[j]]=1;
            if(i%pri[j]==0) break;
        }
    }
    for(int i=0;i<p;i++) {
        ph[i][0]=1;
        for(int j=1;j<p;j++) {
            ph[i][j]=ph[i][j-1]*pri[i];
            if(ph[i][j]<0) ph[i][j]=0;
        }
    }
    dfs(0, p-1, 1, 1);
    cout<<pl2<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-1463.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆