deepseek之力

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

using ULL = unsigned long long;
using LD = long double;

// 快速幂 (a^e) % mod
ULL pow_mod(ULL a, ULL e, ULL mod) {
    ULL res = 1 % mod;
    a %= mod;
    while (e) {
        if (e & 1) res = (__int128)res * a % mod;
        a = (__int128)a * a % mod;
        e >>= 1;
    }
    return res;
}

struct Gen {
    LD log_val;
    int prime;
    ULL num, den;
};

struct Element {
    LD log_val;
    ULL num, den;
    int parent, gen_idx;
    int c2, sum_odd;       // 路径上 gen=2 的次数 / gen!=2 的次数
};

struct Candidate {
    LD log_val;
    ULL num, den;
    int gen_idx;

    bool operator>(const Candidate& o) const {
        if (fabsl(log_val - o.log_val) > 1e-15L)
            return log_val > o.log_val;
        // 精确比较避免浮点误差
        return (__int128)num * o.den > (__int128)o.num * den;
    }
};

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

    int n; ULL p_mod;
    cin >> n >> p_mod;

    // ---------- 筛素数 ----------
    const int MAX_P = 2000000;
    vector<bool> is_prime(MAX_P + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= MAX_P; ++i)
        if (is_prime[i])
            for (int j = i * i; j <= MAX_P; j += i)
                is_prime[j] = false;
    vector<int> odd_primes;
    for (int i = 3; i <= MAX_P; ++i)
        if (is_prime[i])
            odd_primes.push_back(i);

    // ---------- 构造生成元 ----------
    vector<Gen> G;
    // 1.5 = 3/2
    G.push_back({logl(1.5L), 3, 3ULL, 2ULL});
    // 2 = 2/1
    G.push_back({logl(2.0L), 2, 2ULL, 1ULL});
    // p/2  (p = 5,7,11,...)
    for (size_t i = 1; i < odd_primes.size(); ++i) {
        int p = odd_primes[i];
        LD val = p / 2.0L;
        G.push_back({logl(val), p, (ULL)p, 2ULL});
    }

    // 实际使用的生成元个数，保证足够多
    int K = min((int)G.size(), max(100000, n + 50000));

    // ---------- 优先队列生成乘数 ----------
    vector<Element> A;
    A.reserve(n + 10);
    // 第一个乘数 1
    A.push_back({0.0L, 1ULL, 1ULL, -1, -1, 0, 0});

    vector<int> ptr(K, 0);
    priority_queue<Candidate, vector<Candidate>, greater<Candidate>> pq;

    for (int i = 0; i < K; ++i) {
        pq.push({G[i].log_val, G[i].num, G[i].den, i});
    }

    int valid_cnt = 1;          // A[0] 已经满足条件 (e2 = n >= 0)
    int target_idx = 0;         // 第 n 个满足条件的乘数在 A 中的下标

    while (valid_cnt < n) {
        Candidate cand = pq.top(); pq.pop();
        ULL cur_num = cand.num, cur_den = cand.den;
        int gen_idx = cand.gen_idx;
        int base = ptr[gen_idx];          // 产生该候选的基下标

        // 计算该候选的 c2 和 sum_odd
        int new_c2 = A[base].c2 + (gen_idx == 1 ? 1 : 0);
        int new_sum_odd = A[base].sum_odd + (gen_idx != 1 ? 1 : 0);
        bool valid = ((ULL)n + new_c2 >= (ULL)new_sum_odd);

        bool dup = (cur_num == A.back().num && cur_den == A.back().den);
        if (!dup) {
            A.push_back({cand.log_val, cur_num, cur_den, base, gen_idx, new_c2, new_sum_odd});
            if (valid) {
                ++valid_cnt;
                if (valid_cnt == n) target_idx = A.size() - 1;
            }
        }

        // 推进该生成元的指针并产生新的候选
        ptr[gen_idx]++;
        if (ptr[gen_idx] < (int)A.size()) {
            int nb = ptr[gen_idx];
            ULL new_num = A[nb].num * G[gen_idx].num;
            ULL new_den = A[nb].den * G[gen_idx].den;
            LD new_log = A[nb].log_val + G[gen_idx].log_val;
            pq.push({new_log, new_num, new_den, gen_idx});
        }

        // 处理堆中所有值与当前值相等的重复候选
        while (!pq.empty()) {
            if (pq.top().num == cur_num && pq.top().den == cur_den) {
                Candidate dup_cand = pq.top(); pq.pop();
                int i = dup_cand.gen_idx;
                ptr[i]++;
                if (ptr[i] < (int)A.size()) {
                    int nb = ptr[i];
                    ULL new_num = A[nb].num * G[i].num;
                    ULL new_den = A[nb].den * G[i].den;
                    LD new_log = A[nb].log_val + G[i].log_val;
                    pq.push({new_log, new_num, new_den, i});
                }
            } else break;
        }
    }

    // ---------- 回溯得到生成元使用次数 ----------
    vector<ULL> cnt(K, 0);
    int cur = target_idx;
    while (cur != 0) {
        int g = A[cur].gen_idx;
        cnt[g]++;
        cur = A[cur].parent;
    }

    ULL c2 = cnt[1];
    ULL sum_odd = 0;
    for (int i = 0; i < K; ++i)
        if (i != 1) sum_odd += cnt[i];

    long long e2 = (long long)n + (long long)c2 - (long long)sum_odd;
    // 理论上 e2 >= 0，保险处理
    if (e2 < 0) e2 = 0;

    // ---------- 计算最终答案 ----------
    ULL ans = pow_mod(2ULL, (ULL)e2, p_mod);
    for (int i = 0; i < K; ++i) {
        if (i == 1) continue;
        if (cnt[i] > 0) {
            ans = (__int128)ans * pow_mod((ULL)G[i].prime, cnt[i], p_mod) % p_mod;
        }
    }

    cout << ans << '\n';
    return 0;
}

SB

这题很难，同意的点赞

一看你就是来抄题解的