问题分析

本题需要维护一个序列，支持四种操作：

• 区间LCM查询：计算区间内所有数的最小公倍数模 $p$ 的值
• 区间GCD查询：计算区间内所有数的最大公约数模 $p$ 的值
• 区间赋值：将区间内所有数修改为同一个值
• 公因数个数查询：计算区间内所有数的公因数个数模 $p$ 的值

关键约束：数值范围始终在 $[1, 100]$ 之间。

核心思路

质因数编码

由于值域很小（1-100），可以将每个数用其质因数分解的编码表示：

unsigned long long code[101];

编码设计：

• 使用64位无符号整数编码
• 低32位：存储小质数（2,3,5,7）的指数，每个质数用8位存储
• 高32位：用位掩码表示其他质数（≥11）是否存在
• 最高位：标记有效编码

数学性质利用

GCD与LCM的编码运算：

• GCD编码 = 所有数编码的按位与
• LCM编码 = 所有数编码的按位或

这是因为：

• GCD需要取每个质因数的最小指数 → 按位与
• LCM需要取每个质因数的最大指数 → 按位或

线段树维护

使用线段树维护区间GCD和LCM的编码：

struct node_type {
    unsigned long long gcd_code, lcm_code;
    unsigned long long tag;  // 懒标记
};

算法实现

1. 预处理阶段

质数筛法：

void sieve() {
    // 筛出1-100的所有质数，计算每个数的约数个数d[i]
    // 记录每个数的质因数分解信息
}

编码预处理：

void preprocess() {
    for (int i = 1; i <= 100; i++) {
        // 根据质因数分解生成编码
        code[i] = encode_primitive_factors(i);
    }
}

2. 线段树操作

区间查询：

unsigned long long query_gcd_code(int first, int last) {
    // 查询区间GCD编码（按位与）
}

unsigned long long query_lcm_code(int first, int last) {
    // 查询区间LCM编码（按位或）
}

区间修改：

void modify(int first, int last, unsigned long long value) {
    // 区间赋值，使用懒标记
}

3. 编码解码

编码到数值：

int decode_modulo(unsigned long long x, int mod) {
    // 将编码转换回实际数值模mod
    // 根据编码中的质因数信息重建数值
}

复杂度分析

• 预处理：$O(100)$，常数时间
• 线段树构建：$O(n)$
• 每次查询/修改：$O(\log n)$
• 总复杂度：$O((n+q)\log n)$

关键优化

1. 值域限制利用：由于值域很小，可以预处理所有可能数值的编码
2. 位运算优化：使用位运算高效计算GCD和LCM
3. 懒标记：支持高效的区间赋值操作
4. 模运算处理：只在最后解码时进行模运算，避免中间结果溢出

算法步骤

1. 初始化：

   • 预处理1-100所有数的质因数分解和编码
   • 构建线段树，叶子节点存储初始序列的编码

2. 处理操作：

   • L操作：查询区间LCM编码 → 解码模p → 输出
   • G操作：查询区间GCD编码 → 解码模p → 输出
   • C操作：将区间编码修改为指定值的编码
   • S操作：查询区间GCD编码 → 解码得到实际GCD值 → 计算约数个数模p

代码总结

本题通过巧妙的质因数编码技术，将GCD和LCM的区间查询转化为位运算问题，结合线段树实现了高效处理。算法的核心在于充分利用值域小的特点，将数学运算转化为位运算，达到了 $O(\log n)$ 的查询复杂度。

该解法能够处理 $n,q \leq 3\times 10^5$ 的大数据规模，是结合数论知识和数据结构优化的经典范例。