Author: lllyouo
Date: 20250702
tag: 约数、搜索
link: https://www.luogu.com.cn/problem/P1463

问题描述

link

分析

略

参考代码

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

int n, pre[12] = {0, 2, 3, 5, 7, 11, 13, 17, 19,23, 29, 31};
long long sum = -1, ans = -1;

// x 当前数字
// id 当前质因子下标
// c 当前数字的约数个数
// s 当前指数之和
void dfs(long long x, int id, int c, int s) {
    if (c > sum || (c == sum && x < ans)) {
        ans = x, sum = c;
    }

    long long t = x;
    int i = 0;
    while (i < s) {
        i++;
        // 总乘积不超过 n
        if (n / t < pre[id]) return ;
        
        t *= pre[id];
        if (t <= n) {
            dfs(t, id + 1, c * (i + 1), i);
        }
    }
}

int main() {
    cin >> n;

    dfs(1, 1, 1, 30);
    cout << ans << endl;
    
    return 0;
}