A21625 求正整数 全站最快首发题解

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>

const std::vector<int> primes = {
    2,  3,  5,  7, 11, 13, 17, 19, 23, 29,
    31, 37, 41, 43, 47, 53, 59, 61, 67, 71
};
std::vector<long double> log_primes;

int n_val;
long double min_log_m;
std::vector<int> best_exponents;

void search(int prime_idx, int remaining_n, int max_exponent, long double current_log, std::vector<int>& current_exponents) {
    if (current_log >= min_log_m) {
        return;
    }

    if (remaining_n == 1) {
        min_log_m = current_log;
        best_exponents = current_exponents;
        return;
    }

    if (prime_idx >= primes.size()) {
        return;
    }

    for (int i = 1; i <= max_exponent; ++i) {
        if (remaining_n % (i + 1) == 0) {
            long double next_log = current_log + (long double)i * log_primes[prime_idx];
            
            if (next_log >= min_log_m) {
                break;
            }

            current_exponents.push_back(i);
            search(prime_idx + 1, remaining_n / (i + 1), i, next_log, current_exponents);
            current_exponents.pop_back();
        }
    }
}

std::string high_precision_multiply(const std::vector<int>& exponents) {
    std::vector<int> result_digits;
    result_digits.push_back(1);

    for (size_t i = 0; i < exponents.size(); ++i) {
        int prime = primes[i];
        int exponent = exponents[i];
        for (int k = 0; k < exponent; ++k) {
            int carry = 0;
            for (size_t d = 0; d < result_digits.size(); ++d) {
                long long product = (long long)result_digits[d] * prime + carry;
                result_digits[d] = product % 10;
                carry = product / 10;
            }
            while (carry > 0) {
                result_digits.push_back(carry % 10);
                carry /= 10;
            }
        }
    }

    std::string final_result = "";
    for (int i = result_digits.size() - 1; i >= 0; --i) {
        final_result += std::to_string(result_digits[i]);
    }
    return final_result;
}


void solve() {
    std::cin >> n_val;

    for (int p : primes) {
        log_primes.push_back(std::log((long double)p));
    }

    min_log_m = 1e18; 
    std::vector<int> current_exponents;

    search(0, n_val, n_val, 0.0, current_exponents);

    std::cout << high_precision_multiply(best_exponents) << '\n';
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    solve();
    return 0;
}