解题思路

给定长度为 n 的数组，需要处理两类操作：

1. 查询：给定整数 k，统计数组中有多少个数能被 k 整除；
2. 修改：把位置 i 的数改为 x。

若每次查询都线性扫描数组，时间为 O(n)，在 n、q 均为 2×10^5 的规模下会超时。 关键观察：一个数能否被 k 整除，只与它的所有“因子关系”有关。我们可以把问题转化为按“可整除值”统计频次：

• 维护数组中每个取值 v 的出现次数 freq[v]。
• 进一步维护 cntMul[d]：当前数组中能被 d 整除的元素个数。
• 对于查询 1 k，直接输出 cntMul[k]，为 O(1)。
• 对于修改 2 i x，设原值为 old。 我们需要把所有 old 的因子 d 的贡献减去 1（cntMul[d]--）， 再把所有 x 的因子 d 的贡献加上 1（cntMul[d]++），最后更新 a[i]=x。

为使更新高效，我们预处理 1..MAXA 每个数的所有因子（MAXA 为数值上界 2×10^5）。可用类似筛法：

for d in [1..MAXA]:
    for m in [d, 2d, 3d, ... ≤ MAXA]:
        divisors[m].push_back(d)

这样得到 divisors[v] 后：

• 初始建立：遍历数组中每个值 v，把 cntMul[d]++（d ∈ divisors[v]）。
• 单点修改：仅遍历原值和新值的因子集合更新即可。

相关算法：整除筛 / 因子预处理 + 频次统计。 核心思路：把“查询倍数个数”的 O(MAXA/k) 计算，改为 O(1) 查询 + O(因子数) 更新。一个数的因子个数一般很小（最大值 < 128 对本题上界），因此整体复杂度可控。

复杂度分析

• 预处理因子：约为 MAXA * (1/1 + 1/2 + ... + 1/MAXA) = O(MAXA log MAXA)。
• 建表：对每个 a[i] 遍历其因子，代价为 Σ τ(a[i])，其中 τ(x) 为因子数，远小于 MAXA。
• 每次查询：O(1)。
• 每次修改：O(τ(old) + τ(x))，通常 ≤ 2×128。
• 额外空间：存储 divisors[1..MAXA]、cntMul[1..MAXA]、freq[1..MAXA]，为 O(MAXA + 总因子数)，约 O(MAXA log MAXA)。

在题目数据范围内完全可行。

代码实现

Python

import sys

def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    n = next(it)
    q = next(it)
    a = [0] + [next(it) for _ in range(n)]  # 1-based

    MAXA = 200000  # 题面给定的上界
    # 预处理每个数的所有因子：整除筛
    divisors = [[] for _ in range(MAXA + 1)]
    for d in range(1, MAXA + 1):
        for m in range(d, MAXA + 1, d):
            divisors[m].append(d)

    # 维护“能被 d 整除的数的个数”
    cntMul = [0] * (MAXA + 1)
    # 初始把数组元素贡献加到各自因子上
    for i in range(1, n + 1):
        v = a[i]
        for d in divisors[v]:
            cntMul[d] += 1

    out_lines = []
    for _ in range(q):
        t = next(it)
        if t == 1:
            k = next(it)
            # 直接输出能被 k 整除的个数
            out_lines.append(str(cntMul[k]))
        else:
            i = next(it)
            x = next(it)
            old = a[i]
            if old == x:
                a[i] = x
                continue
            # 从所有 old 的因子中减去贡献
            for d in divisors[old]:
                cntMul[d] -= 1
            # 给所有 x 的因子增加贡献
            for d in divisors[x]:
                cntMul[d] += 1
            a[i] = x

    sys.stdout.write("\n".join(out_lines))

# 主函数：只做输入输出调度
if __name__ == "__main__":
    solve()

Java

import java.io.*;
import java.util.*;

public class Main {
    // 读取整数的简洁输入（基于 BufferedInputStream，适配大数据）
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= 32);
            if (c == '-') { sgn = -1; c = read(); }
            while (c > 32) {
                x = x * 10 + (c - '0');
                c = read();
            }
            return x * sgn;
        }
    }

    static void solve(FastScanner fs) throws Exception {
        int n = fs.nextInt();
        int q = fs.nextInt();
        int[] a = new int[n + 1];
        int MAXA = 200000;

        for (int i = 1; i <= n; i++) a[i] = fs.nextInt();

        // 预处理每个数的所有因子
        ArrayList<Integer>[] divisors = new ArrayList[MAXA + 1];
        for (int i = 0; i <= MAXA; i++) divisors[i] = new ArrayList<>();
        for (int d = 1; d <= MAXA; d++) {
            for (int m = d; m <= MAXA; m += d) {
                divisors[m].add(d);
            }
        }

        // 维护能被 d 整除的数量
        int[] cntMul = new int[MAXA + 1];
        for (int i = 1; i <= n; i++) {
            int v = a[i];
            for (int d : divisors[v]) cntMul[d]++;
        }

        StringBuilder sb = new StringBuilder();
        for (int qi = 0; qi < q; qi++) {
            int t = fs.nextInt();
            if (t == 1) {
                int k = fs.nextInt();
                sb.append(cntMul[k]).append('\n');
            } else {
                int idx = fs.nextInt();
                int x = fs.nextInt();
                int old = a[idx];
                if (old != x) {
                    for (int d : divisors[old]) cntMul[d]--;
                    for (int d : divisors[x]) cntMul[d]++;
                    a[idx] = x;
                } else {
                    a[idx] = x;
                }
            }
        }
        System.out.print(sb.toString());
    }

    // 主函数：只做输入输出调度
    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        solve(fs);
    }
}

C++

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

void solve() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    if (!(cin >> n >> q)) return;
    const int MAXA = 200000;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    // 预处理每个数的所有因子：整除筛
    vector<vector<int>> divisors(MAXA + 1);
    for (int d = 1; d <= MAXA; ++d) {
        for (int m = d; m <= MAXA; m += d) {
            divisors[m].push_back(d);
        }
    }

    // 维护能被 d 整除的数量
    vector<int> cntMul(MAXA + 1, 0);
    for (int i = 1; i <= n; ++i) {
        for (int d : divisors[a[i]]) cntMul[d]++;
    }

    // 处理操作
    for (int _ = 0; _ < q; ++_) {
        int t; cin >> t;
        if (t == 1) {
            int k; cin >> k;
            cout << cntMul[k] << '\n';
        } else {
            int i, x; cin >> i >> x;
            int old = a[i];
            if (old != x) {
                for (int d : divisors[old]) cntMul[d]--;
                for (int d : divisors[x])  cntMul[d]++;
                a[i] = x;
            } else {
                a[i] = x;
            }
        }
    }
}

// 主函数：只做输入输出调度
int main() {
    solve();
    return 0;
}

题目内容

给定一个长度为 $n$ 的数组 {$a_1,a_2,...,a_n$}。你需要依次处理 $q$ 次操作，每次操作属于两种类型之一:

查询:给定整数 $k$ ，统计整个数组中有多少个数可以被 $k$ 整除;

修改:将位置 $i$ 的数值改为 $2$ (数组下标从 $1$ 开始)。

输入描述

第一行输入两个整数 $n,q(1 ≦ n,q ≦ 2× 10^5)$，表示数组长度与操作次数

第二行输入 $n$ 个整数 $a_1,a_2,…,a_n(1 ≦ a_i ≦ 2× 10^5)$，表示初始数组

此后 $q$ 行，每行表示一次操作:

若为查询，输入两个整数 $1$ $k(1≤k≤2× 10^5)$

若为修改，输入三个整数 $2$ $i$ $x(1≦i≦n;1≦x≦2×10^5)$

输出描述

对于每一次查询操作，输出一行答案

样例1

输入

5 6
2 3 4 5 6
1 2
1 3
2 3 9
1 3
2 5 12
1 6

输出

3
2
3
1

说明

初始数组为 {$2,3,4,5,6$}

查询 $k = 2$ :可整除的为 {$2,4,6$}，答案为 $3$ 。

查询 $k = 3$ :可整除的为 {$3,6$}，答案为 $2$ ;