求 hack
查看原帖
求 hack
682739
nr0728楼主2024/9/14 15:05
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long ll;

ll L, U;
ll max_D;
ll P;

// 生成小于等于 max_prime 的所有质数
vector<int> generate_primes(int max_prime) {
    vector<bool> is_prime(max_prime + 1, true);
    vector<int> primes;
    is_prime[0] = is_prime[1] = false;
    for(int i = 2; i <= max_prime; ++i) {
        if(is_prime[i]) {
            primes.push_back(i);
            for(int j = i + i; j <= max_prime; j += i)
                is_prime[j] = false;
        }
    }
    return primes;
}

// 递归搜索
void dfs(const vector<int>& primes, int idx, ll N, ll D, int last_exp) {
    if(N > U) return;
    if(N >= L) {
        if(D > max_D || (D == max_D && N < P)) {
            max_D = D;
            P = N;
        }
    }
    for(int i = idx; i < primes.size(); ++i) {
        int prime = primes[i];
        for(int exp = 1; exp <= last_exp; ++exp) {
            if(N > U / prime) break; // 防止乘积溢出
            ll N_new = N;
            bool overflow = false;
            for(int e = 0; e < exp; ++e) {
                N_new *= prime;
                if(N_new > U) {
                    overflow = true;
                    break;
                }
            }
            if(overflow) break;
            ll D_new = D * (exp + 1);
            dfs(primes, i + 1, N_new, D_new, exp);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> L >> U;

    const ll SMALL_INTERVAL = 1e7;

    max_D = 0;
    P = U + 1;

    if(U - L <= SMALL_INTERVAL) {
        // 小区间,使用暴力方法
        int N = U - L + 1;
        vector<int> divisors(N, 1);
        vector<ll> numbers(N);
        for(int i = 0; i < N; ++i)
            numbers[i] = L + i;

        vector<ll> num_remain = numbers;

        for(ll p = 2; p * p <= U; ++p) {
            for(ll j = ((L + p - 1) / p) * p; j <= U; j += p) {
                int cnt = 0;
                while(num_remain[j - L] % p == 0) {
                    num_remain[j - L] /= p;
                    cnt++;
                }
                if(cnt > 0) {
                    divisors[j - L] *= (cnt + 1);
                }
            }
        }

        for(int i = 0; i < N; ++i) {
            if(num_remain[i] > 1) {
                divisors[i] *= 2;
            }
            if(divisors[i] > max_D || (divisors[i] == max_D && numbers[i] < P)) {
                max_D = divisors[i];
                P = numbers[i];
            }
        }
    } else {
        // 大区间,使用递归方法
        vector<int> primes = generate_primes(100); // 生成小于等于 100 的质数

        dfs(primes, 0, 1, 1, 30); // 递归搜索,指数最大值设为 30

        // 如果没有找到符合条件的数,使用暴力方法在 [L, L+SMALL_INTERVAL] 内搜索
        if(max_D == 0) {
            U = L + SMALL_INTERVAL;
            int N = U - L + 1;
            vector<int> divisors(N, 1);
            vector<ll> numbers(N);
            for(int i = 0; i < N; ++i)
                numbers[i] = L + i;

            vector<ll> num_remain = numbers;

            for(ll p = 2; p * p <= U; ++p) {
                for(ll j = ((L + p - 1) / p) * p; j <= U; j += p) {
                    int cnt = 0;
                    while(num_remain[j - L] % p == 0) {
                        num_remain[j - L] /= p;
                        cnt++;
                    }
                    if(cnt > 0) {
                        divisors[j - L] *= (cnt + 1);
                    }
                }
            }

            for(int i = 0; i < N; ++i) {
                if(num_remain[i] > 1) {
                    divisors[i] *= 2;
                }
                if(divisors[i] > max_D || (divisors[i] == max_D && numbers[i] < P)) {
                    max_D = divisors[i];
                    P = numbers[i];
                }
            }
        }
    }

    cout << "Between " << L << " and " << U << ", " << P << " has a maximum of " << max_D << " divisors.\n";

    return 0;
}
2024/9/14 15:05
加载中...