题意分析

给定若干个正整数 $p$，需对每个 $p$ 计算 Lucas–Lehmer 数列 $s_0=4,\quad s_i = s_{i-1}^2-2$ 直到 $i=p-2$，然后取模 $M_p=2^p-1$，输出余数 $s_{p-2}\bmod M_p$ 的十六进制表示。

解题思路

• 处理大整数运算：当 $p$ 较大（可达近 8000）时，$M\_p=2^p-1$ 和中间的 $s\_i$ 都非常大，需要用“高精度”方式存储和运算。
• 处理模 $2^p-1$ 折叠：利用 Mersenne 模数的性质，任何大整数对 $2^p-1$ 取模，都可以将其二进制表示中高于第 $p$ 位的部分“折叠”到低位，然后再减去一次或多次 $2^p-1$ 完成最终模运算，复杂度约 $O(W)$，其中 $W=\lceil p/32\rceil$。
• Lucas–Lehmer 的迭代：从 $s=4$ 开始，重复 $p-2$ 次“平方、折叠模、减 2”操作，结束后判断 $s$ 是否为零（即余数是否为 0）。

本题代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>
using namespace std;

typedef uint32_t u32;
typedef uint64_t u64;
typedef int64_t  i64;

// 模拟大整数，每个元素存 32 位，低位在前
struct Big {
    vector<u32> a;
    Big(int W): a(W, 0) {}

    // 是否为 0
    bool is_zero() const {
        for (u32 v : a) if (v) return false;
        return true;
    }
    // 大小比较：>=
    bool ge(const Big &b) const {
        for (int i = (int)a.size()-1; i >= 0; --i) {
            if (a[i] != b.a[i]) return a[i] > b.a[i];
        }
        return true;
    }
    // 原地加法：this += b
    void add_inplace(const Big &b) {
        u64 carry = 0;
        for (size_t i = 0; i < a.size(); ++i) {
            u64 sum = carry + a[i] + b.a[i];
            a[i] = (u32)sum;
            carry = sum >> 32;
        }
    }
    // 原地减法：this -= b（保证 *this >= b）
    void sub_inplace(const Big &b) {
        i64 borrow = 0;
        for (size_t i = 0; i < a.size(); ++i) {
            i64 diff = (i64)a[i] - b.a[i] + borrow;
            if (diff < 0) {
                diff += (1LL<<32);
                borrow = -1;
            } else {
                borrow = 0;
            }
            a[i] = (u32)diff;
        }
    }
    // 返回原始乘积，长度 2W
    vector<u32> mul_raw(const Big &b) const {
        int W = a.size();
        vector<u32> c(2*W, 0);
        for (int i = 0; i < W; ++i) {
            u64 carry = 0;
            for (int j = 0; j < W; ++j) {
                u64 t = (u64)a[i] * b.a[j] + c[i+j] + carry;
                c[i+j] = (u32)t;
                carry = t >> 32;
            }
            c[i+W] = (u32)carry;
        }
        return c;
    }
    // 右移 bits 位（bits < 32）
    static Big shr_bits(const Big &x, int bits) {
        int W = x.a.size();
        Big r(W);
        u32 carry = 0;
        for (int i = W-1; i >= 0; --i) {
            u32 cur = x.a[i];
            r.a[i] = (cur >> bits) | (carry << (32-bits));
            carry = cur & ((1u<<bits)-1);
        }
        return r;
    }
};

// 对 raw = x*x 的 2W 词结果，模 M_p=2^p-1
Big mod_mersenne(const vector<u32> &raw, int p) {
    int W = raw.size()/2;
    int w = p/32, o = p%32;
    Big low(W), high(W);
    // 取低 p 位
    for (int i = 0; i < w; ++i) low.a[i] = raw[i];
    if (o) low.a[w] = raw[w] & ((1u<<o)-1);
    // 取高 p 位
    if (o==0) {
        for (int i = w; i < 2*W && i-w < W; ++i)
            high.a[i-w] = raw[i];
    } else {
        for (int i = w; i < 2*W; ++i) {
            u32 cur = raw[i];
            high.a[i-w] |= cur >> o;
            if (i+1<2*W) {
                u32 hi = raw[i+1] & ((1u<<o)-1);
                high.a[i-w] |= hi << (32-o);
            }
        }
    }
    // 折叠并减模
    low.add_inplace(high);
    Big M(W);
    for (int i = 0; i < w; ++i) M.a[i] = 0xFFFFFFFFu;
    if (o) M.a[w] = (1u<<o)-1;
    if (low.ge(M)) low.sub_inplace(M);
    return low;
}

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

    int p;
    while (cin >> p) {
        if (p < 2) {
            cout << "0\n";
            continue;
        }
        int W = (p+31)/32;
        Big s(W);
        s.a[0] = 4;

        // 迭代计算 s_{i}，直到 i = p-2
        for (int i = 1; i <= p-2; ++i) {
            auto raw = s.mul_raw(s);
            Big t = mod_mersenne(raw, p);
            // 减 2
            if (t.a[0] < 2) {
                u64 tmp = (u64)t.a[0] + (1ULL<<32) - 2;
                t.a[0] = (u32)tmp;
                u64 borrow = ((tmp>>32)==0) ? 1 : 0;
                int k = 1;
                while (borrow && k < W) {
                    u64 tmp2 = (u64)t.a[k] - borrow;
                    if ((i64)tmp2 < 0) {
                        tmp2 += (1ULL<<32);
                        borrow = 1;
                    } else {
                        borrow = 0;
                    }
                    t.a[k++] = (u32)tmp2;
                }
            } else {
                t.a[0] -= 2;
            }
            s = t;
        }

        // 输出十六进制余数
        if (s.is_zero()) {
            cout << "0\n";
        } else {
            string hex;
            Big tmp = s;
            while (!tmp.is_zero()) {
                u32 d = tmp.a[0] & 0xF;
                hex.push_back(d<10 ? char('0'+d) : char('a'+d-10));
                tmp = Big::shr_bits(tmp,4);
            }
            reverse(hex.begin(), hex.end());
            cout << hex << "\n";
        }
    }
    return 0;
}