「动态乘除查询」题解

问题分析

我们需要处理一系列乘法和除法操作：

• 类型1：将当前值乘以 m
• 类型2：撤销第 pos 次操作（该操作必须是类型1，且每个类型1操作最多被撤销一次）

每次操作后需要输出当前值对 M 取模的结果。

核心难点

1. 大数运算：Q最大可达 10^5，M最大可达 10^9，直接计算乘积会溢出，且不能直接存储原始值
2. 除法处理：模运算中的除法不是简单的模逆元，因为 M 不一定是质数
3. 撤销操作：需要高效地撤销之前的乘法操作

解法思路

方法1：质因数分解法（推荐）

核心思想

将每次乘法/除法操作转化为对质因数的加减操作：

1. 对 M 进行质因数分解：M = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ
2. 维护当前值 x 对每个质因数的指数
3. 维护不能被 M 的质因数整除的部分（与 M 互质的部分）

具体步骤

1. 预处理：

   • 对 M 进行质因数分解，得到质因数列表 primes 和对应指数 exps
   • 创建一个数组 cnt 记录当前 x 对每个质因数的指数
   • 维护一个变量 cur 记录当前值与 M 互质的部分

2. 类型1操作（乘法）：

   • 对 m 进行质因数分解，将其拆分为两部分：
     • 与 M 共享质因数的部分：更新对应的 cnt 数组
     • 与 M 互质的部分：更新 cur 值
   • 计算当前结果：result = cur × Π(primes[i]^cnt[i]) % M

3. 类型2操作（除法）：

   • 找到第 pos 次操作的乘数 m
   • 对 m 进行质因数分解，从 cnt 数组中减去对应质因数的指数
   • 将 m 中与 M 互质的部分用扩展欧几里得算法求逆元，更新 cur

4. 结果计算：

   • 需要快速计算 Π(primes[i]^cnt[i]) % M
   • 可以使用快速幂算法

方法2：线段树/树状数组法

核心思想

• 维护一个序列，记录每个操作的有效性
• 计算当前所有有效操作的乘积模 M
• 类型2操作相当于将某个操作标记为无效

具体步骤

1. 维护一个线段树或树状数组，每个叶子节点存储对应操作的乘数（类型1）或1（类型2）
2. 类型1操作：在对应位置插入 m
3. 类型2操作：将第 pos 次操作的位置值设为1（相当于除以 m）
4. 查询：求整个区间的乘积模 M

局限性

• 当 M 不是质数时，无法直接处理除法
• 需要记录每个操作的位置

方法3：记录操作序列法

核心思想

• 维护一个操作序列数组
• 记录每个类型1操作是否被撤销
• 重新计算当前乘积时，只乘上未被撤销的操作

具体步骤

1. 创建数组 ops[] 记录所有操作
2. 创建数组 valid[] 记录每个操作是否有效
3. 类型1操作：添加 m 到 ops，标记为有效
4. 类型2操作：将第 pos 次操作标记为无效
5. 每次操作后，重新遍历所有有效操作计算乘积

时间复杂度

• 最坏情况 O(Q²)，会超时

推荐实现：质因数分解法

import sys
import math

def factorize(n):
    """质因数分解"""
    factors = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1 if d == 2 else 2
    if n > 1:
        factors[n] = factors.get(n, 0) + 1
    return factors

def extended_gcd(a, b):
    """扩展欧几里得算法，返回 (gcd, x, y) 满足 ax + by = gcd(a, b)"""
    if b == 0:
        return a, 1, 0
    gcd, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return gcd, x, y

def mod_inverse(a, mod):
    """求 a 在模 mod 下的逆元，需要 gcd(a, mod) = 1"""
    gcd, x, _ = extended_gcd(a, mod)
    if gcd != 1:
        return None  # 逆元不存在
    return x % mod

def solve():
    input_data = sys.stdin.read().split()
    t = int(input_data[0])
    idx = 1
    results = []
    
    for _ in range(t):
        Q, M = int(input_data[idx]), int(input_data[idx+1])
        idx += 2
        
        # 对 M 进行质因数分解
        m_factors = factorize(M)
        primes = list(m_factors.keys())
        prime_count = len(primes)
        
        # 当前值 x 的质因数指数
        cnt = [0] * prime_count
        # 当前值中与 M 互质的部分
        cur = 1
        
        # 存储所有类型1操作的乘数及其质因数分解
        multipliers = [None] * (Q + 1)
        # 存储操作结果
        outputs = []
        
        for i in range(1, Q + 1):
            op = int(input_data[idx])
            val = int(input_data[idx+1])
            idx += 2
            
            if op == 1:
                m = val
                multipliers[i] = m
                
                # 对 m 进行质因数分解，分离出与 M 共享的质因数
                temp = m
                coprime_part = 1
                
                for j, p in enumerate(primes):
                    exp = 0
                    while temp % p == 0:
                        exp += 1
                        temp //= p
                    cnt[j] += exp
                    if exp > 0:
                        coprime_part *= pow(p, exp)
                
                # temp 现在是与 M 互质的部分
                cur = (cur * temp) % M
                
                # 计算当前结果
                result = cur
                for j in range(prime_count):
                    if cnt[j] > 0:
                        result = (result * pow(primes[j], cnt[j], M)) % M
                
                outputs.append(result)
                
            else:  # op == 2
                pos = val
                m = multipliers[pos]
                
                # 对 m 进行质因数分解，从 cnt 中减去
                temp = m
                coprime_part = 1
                
                for j, p in enumerate(primes):
                    exp = 0
                    while temp % p == 0:
                        exp += 1
                        temp //= p
                    cnt[j] -= exp
                
                # temp 现在是与 M 互质的部分
                # 需要求 temp 在模 M 下的逆元
                if temp > 1:
                    inv = mod_inverse(temp, M)
                    if inv is not None:
                        cur = (cur * inv) % M
                
                # 计算当前结果
                result = cur
                for j in range(prime_count):
                    if cnt[j] > 0:
                        result = (result * pow(primes[j], cnt[j], M)) % M
                
                outputs.append(result)
        
        results.extend(outputs)
    
    # 输出所有结果
    print("\n".join(map(str, results)))

if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度

• 质因数分解 M：O(√M)，但 M ≤ 10^9，√M ≈ 31623，可接受
• 每次操作：
  • 质因数分解 m：O(√m)，但 m 是输入的乘数，实际较小
  • 更新质因数指数：O(k)，k 是 M 的不同质因数个数（不超过 9 个）
  • 计算当前值：O(k)
• 总时间复杂度：O(Q × (√m + k))，在 Q=10^5 时可接受

空间复杂度

• O(k + Q)，k 是 M 的质因数个数，Q 是操作数

样例验证

以题目样例为例：

输入：
1
10 1000000000
1 2
2 1
1 2
1 10
2 3
2 4
1 6
1 7
1 12
2 7

输出：
2
1
2
20
10
1
6
42
504
84

逐步验证：

1. ×2 → 2
2. ÷2(第1次) → 1
3. ×2 → 2
4. ×10 → 20
5. ÷2(第3次) → 10
6. ÷10(第4次) → 1
7. ×6 → 6
8. ×7 → 42
9. ×12 → 504
10. ÷7(第8次) → 84

与输出完全一致。

注意事项

1. 逆元存在条件：只有当数与模数互质时，模逆元才存在。本题中，我们只对与 M 互质的部分求逆元。
2. M=1 的特殊情况：需要特殊处理，所有结果都是 0。
3. 乘数为 0：题目没有明确说明，但一般不会出现乘数为 0 的情况，因为需要支持撤销操作。
4. 性能优化：可以使用预计算的质因数分解和快速幂来加速计算。

这个解法能够高效处理大规模数据，满足题目要求的时间限制。