题解

题目概述

本题是一个多功能评测框架，需要根据输入的功能编号执行不同的算法任务。主要涉及数论和密码学相关算法。

功能模块解析

1. 19的幂次计算 (1_998244353, 1?, 1?+)

算法思路

使用快速幂算法计算 $19^n \bmod p$，其中 $p$ 分别为：

• 1_998244353: $p = 998244353$
• 1?: $p = 1145141$
• 1?+: $p = 5211600617818708273$

关键代码

LL qmi(LL a, LL b, LL mod) {
    LL res = 1;
    while (b) {
        if (b & 1) res = (LLL)res * a % mod;
        a = (LLL)a * a % mod;
        b >>= 1;
    }
    return res;
}

// 读入指数并对(mod-1)取模
LL read(LL mod) {
    LL x = 0;
    char c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        x %= mod;
        c = getchar();
    }
    return x;
}

数学原理

根据费马小定理：当 $p$ 为质数时，$a^{p-1} \equiv 1 \pmod{p}$，因此指数可以对 $p-1$ 取模。

2. 溢出处理 (1wa_998244353)

算法思路

发现 $19^n \bmod 998244353$ 在 $n > 55244$ 后出现周期为 $45699$ 的循环，通过预处理和周期性质优化计算。

关键代码

void init() {
    pow19[0] = 1;
    for (int i = 1; i < start_repeat + repeat_len; i++)
        pow19[i] = pow19[i-1] * 19 % mod;
}

void solve() {
    if (x > start_repeat)
        x = (x - start_repeat) % repeat_len + start_repeat;
    printf("%d\n", pow19[x]);
}

3. 质数判定 (2p)

算法思路

使用 Miller-Rabin 素性测试算法，基于费马小定理和二次探测定理。

关键代码

bool Miller_Rabin(LL n) {
    if (n <= 2 || !(n & 1)) return n == 2;
    
    LL a = n - 1, b = 0;
    while (!(a & 1)) a >>= 1, b++;
    
    for (int i = 1; i <= 10; i++) {
        LL x = rand() % (n-2) + 2, v = qmi(x, a, n);
        if (v == 1) continue;
        
        for (int j = 0; j < b && v != n-1; j++)
            v = (LLL)v * v % n;
            
        if (v != n-1) return false;
    }
    return true;
}

数学原理

• 费马小定理：如果 $p$ 是质数，则对于任意 $a \not\equiv 0 \pmod{p}$，有 $a^{p-1} \equiv 1 \pmod{p}$
• 二次探测定理：如果 $p$ 是奇质数，则 $x^2 \equiv 1 \pmod{p}$ 的解只有 $x \equiv \pm 1 \pmod{p}$

4. 莫比乌斯函数计算 (2u)

算法思路

结合线性筛和区间筛计算莫比乌斯函数 $\mu(n)$：

1. 先用线性筛预处理小质数
2. 对区间内每个数用预处理的质数进行初步分解
3. 对剩余的大因子用 Miller-Rabin 判断是否为质数

关键代码

void init(int n) {
    for (int i = 2; i <= n; i++) {
        if (!minp[i]) primes[++cnt] = i, minp[i] = i;
        for (int j = 1; j <= cnt && primes[j] <= n/i && primes[j] <= minp[i]; j++)
            minp[i * primes[j]] = primes[j];
    }
}

// 区间筛计算莫比乌斯函数
for (int i = 1; i <= cnt; i++) {
    int p = primes[i];
    for (LL j = (l + p - 1) / p * p; j <= r; j += p) {
        if (j % ((LL)p * p)) 
            mu[j - l] = -mu[j - l];
        else 
            mu[j - l] = 0;
        rest[j - l] /= p;
    }
}

// 处理剩余的大质因子
for (int i = 0; i <= r - l; i++) {
    if (mu[i] && rest[i] != 1) {
        if (Miller_Rabin(rest[i]))
            mu[i] *= -1;
        else if (sqr(sqrt(rest[i]) + 0.5) == rest[i])
            mu[i] = 0;
    }
}

莫比乌斯函数定义

$$\mu(n) = \begin{cases} 1 & \text{if } n = 1 \\ (-1)^k & \text{if } n = p_1p_2\cdots p_k \ (p_i \text{为互异质数}) \\ 0 & \text{if } n \text{ 被某个质数的平方整除} \end{cases} $$

5. 原根判定 (2g, 2g?)

算法思路

判断数 $g$ 是否为模 $p$ 的原根：

• 对于特殊模数 $13123111$，利用已知原根 $6$ 和预处理
• 对于一般情况，检查 $g^{(p-1)/q} \not\equiv 1 \pmod{p}$ 对所有 $p-1$ 的质因子 $q$

关键代码

void solve_others(int l, int r, int p) {
    int x = p - 1; 
    top = 0;
    // 分解p-1的质因子
    for (int i = 2; i <= x / i; i++)
        if (!(x % i)) {
            while (!(x % i)) x /= i;
            fac[top++] = i;
        }
    if (x > 1) fac[top++] = x;
    
    for (int i = l; i <= r; i++) {
        bool ok = true;
        for (int j = 0; j < top; j++)
            if (qmi(i, (p-1)/fac[j], p) == 1) {
                ok = false; 
                break;
            }
        putchar(ok ? 'g' : '.');
    }
}

原根判定定理

$g$ 是模 $p$ 的原根当且仅当对于 $p-1$ 的每个质因子 $q$，都有：

$$g^{(p-1)/q} \not\equiv 1 \pmod{p}$$

算法复杂度分析

功能	时间复杂度	空间复杂度	关键优化
19的幂次	$O(\log n)$	$O(1)$	快速幂 + 费马小定理
质数判定	$O(k\log^3 n)$		Miller-Rabin + 二次探测
莫比乌斯函数	$O((r-l)\log\log r)$	$O(r-l + \sqrt{r})$	区间筛 + 线性筛预处理
原根判定	$O((r-l)\log p)$	$O(\log p)$	质因数分解 + 快速幂

关键技术点

1. 大数处理技术

• 使用 __int128_t 防止中间结果溢出
• 模运算的优化实现

2. 数论算法优化

• 快速幂：二进制分解指数，$O(\log n)$ 计算幂次
• Miller-Rabin：10次测试保证正确性，结合费马测试和二次探测
• 区间筛法：避免对每个数单独分解质因数
• 线性筛：$O(n)$ 预处理质数和最小质因子

3. 周期性质利用

在 1wa_998244353 中，通过实验发现：

• 循环起点：$n = 55244$
• 循环周期：$45699$ 利用这一性质将大指数映射到预处理范围内。

4. 特殊情形处理

• 对模数 $13123111$ 使用已知原根 $6$ 进行预处理
• 对莫比乌斯函数中的平方因子进行特殊判断

实现细节

输入处理

// 大数读入并对(mod-1)取模
LL read(LL mod) {
    LL x = 0;
    char c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        x %= mod;  // 实时取模防止溢出
        c = getchar();
    }
    return x;
}

错误处理

class No_such_operation : public std::exception {
public:
    const char *what() const throw() {
        return "No such operation";
    }
};

总结

本题综合考察了：

1. 数论基础：质数判定、原根、莫比乌斯函数
2. 算法设计：快速幂、素性测试、筛法
3. 工程实现：大数处理、特殊情况优化、模块化设计
4. 数学洞察：周期性质发现、算法正确性证明

通过灵活运用各种数学性质和优化技巧，可以在给定的时间限制内完成所有功能模块的计算任务。