Moe's CF Life

喵~ 主人，欢迎来到我的题解小屋！今天我们要解决的是一道关于啤酒、架子和很多很多数学的有趣问题，喵~ 别担心，我会一步一步引导你，让它变得像玩毛线球一样简单，嘻嘻。

题目大意

这道题是说，有一个能干的酒保 Mike，他有一个神奇的架子。架子上有 n 种啤酒，第 i 种啤酒的泡沫高度是 a_i。

一开始架子是空的。接下来会有 q 次操作。每次操作会给一个啤酒的编号 x。

如果编号为 x 的啤酒已经在架子上了，Mike 就会把它拿下来。
如果不在，Mike 就会把它放上去。

每次操作结束后，我们需要计算架子的“得分”。得分的计算方法有点奇特：它是指架子上所有啤酒对 (i, j) 中，满足 i < j 并且它们泡沫高度的最大公约数 gcd(a_i, a_j) 等于 1 的对数。

简单来说，就是每次操作后，告诉老板架子上有多少对泡沫高度互质的啤酒，喵~

解题思路

如果每次操作后，我们都傻乎乎地把架子上所有的啤酒两两组合，再一个个去算 gcd，那肯定会超时喵！你想想，如果架子上有 k 瓶酒，检查所有对就需要 O(k^2) 的时间，q 次查询下来，老板的胡子都等白了。

所以，我们要找一个更聪明的办法！关键在于，每次操作只涉及一瓶啤酒的加入或移除。我们是不是可以只计算这一瓶啤酒带来的得分变化量呢？

当加入一瓶泡沫高度为 v 的啤酒时：新增加的得分，就是这瓶新来的啤酒和架上已经存在的啤酒能组成多少个互质对。也就是，我们需要计算架上有多少瓶酒 u，满足 gcd(v, u) = 1。
当移除一瓶泡沫高度为 v 的啤酒时：减少的得分，就是这瓶被移除的啤酒和架上剩下的啤酒组成的互质对数量。也就是，我们需要计算架上有多少瓶酒 u，满足 gcd(v, u) = 1。

看吧，问题转化成了一个更集中的小问题：对于一个给定的数 v，如何快速求出当前架子上与它互质的数的个数？

直接一个一个检查还是太慢了，这里就要请出我们数论里的好朋友——容斥原理 (Inclusion-Exclusion Principle) 和 莫比乌斯函数 (Möbius Function) 啦，喵！

假设 v 的质因数分解是 p_1, p_2, ..., p_k。与 v 互质，就意味着这个数不能被 p_1、p_2、...、p_k 中任何一个整除。根据容斥原理，与 v 互质的数的个数等于： [总数]- [能被 p_1 整除的数] - [能被 p_2 整除的数] - ...+ [能被 p_1*p_2 整除的数] + [能被 p_1*p_3 整除的数] + ...- [能被 p_1*p_2*p_3 整除的数] - ......

这个长长的式子，可以用莫比乌斯函数 μ(d) 优雅地表示出来。增加的得分 Δ 可以这样计算： Δ = Σ (μ(d) * C(d)) 其中 d 是 v 的所有无平方因子的约数 (square-free divisors)，C(d) 是当前架子上泡沫高度是 d 的倍数的啤酒数量。

为了实现这个想法，我们需要一些“小工具”：

一个数组 counts[d]，用来记录当前架子上，泡沫高度是 d 的倍数的啤酒有多少瓶。
一个方法，能快速找到一个数 v 的所有无平方因子约数。这可以通过先分解质因数来实现。
预先计算好莫比乌斯函数 μ 的值。

具体操作流程喵~

添加 v = a[x]:
1. 计算 v 与当前架上啤酒能组成的互质对数量 delta。delta = Σ (μ(d) * counts[d])，其中 d 遍历 v 的无平方因子约数。
2. total_score += delta。
3. 然后，把 v 正式“放上”架子。更新 counts 数组：对于 v 的所有约数 d，执行 counts[d]++。
4. 标记 x 已经在架子上了。
移除 v = a[x]:
1. 先把 v 从架子上“拿下来”。更新 counts 数组：对于 v 的所有约数 d，执行 counts[d]--。
2. 计算 v 曾经与架上其他啤酒组成的互质对数量 delta。这个数量等于现在架上与 v 互质的啤酒数量。delta = Σ (μ(d) * counts[d])，其中 d 遍历 v 的无平方因子约数。
3. total_score -= delta。
4. 标记 x 已经不在架子上了。

这个顺序非常重要哦！添加时先计算贡献再更新状态，移除时先更新状态再计算贡献，这样逻辑最清晰，喵~

为了让查询过程跑得飞快，我们需要预处理一些东西：

用线性筛在 O(N) 时间内筛出 1 到 max(a_i) 的莫比乌斯函数 μ 和每个数的最小质因子 spf。
预处理出 1 到 max(a_i) 每个数的所有约数，方便更新 counts 数组。

这样，每次查询的复杂度就只和 a[x] 的约数个数和质因子个数有关了，对于 5*10^5 以内的数据，这是非常快的！

题解代码

这是我为主人的小窝准备好的 C++ 代码，加了一些注释方便理解，喵~

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// 喵~ 加速输入输出，让程序跑得更快！
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

const int MAXA = 500005; // 泡沫高度的最大值
const int MAXN = 200005; // 啤酒种类的最大值

// --- 问题数据 ---
int n, q;
int a[MAXN]; // a[i] 是第 i 种啤酒的泡沫高度
bool on_shelf[MAXN]; // on_shelf[i] 标记第 i 种啤酒是否在架子上
long long counts[MAXA]; // counts[d] 记录架子上泡沫高度是 d 的倍数的啤酒数量
long long total_score = 0; // 当前总分

// --- 预处理数据 ---
int spf[MAXA];  // spf[i] 存储 i 的最小质因子 (Smallest Prime Factor)
int mu[MAXA];   // mu[i] 存储 i 的莫比乌斯函数值
std::vector<int> all_divisors[MAXA]; // all_divisors[i] 存储 i 的所有约数

// --- 查询时用的临时变量，避免重复分配内存 ---
std::vector<int> p_factors_cache; // 存质因子
std::vector<int> sq_free_divs_cache; // 存无平方因子约数

// --- 预处理函数 ---

// 线性筛，用来计算 spf 和 mu
void linear_sieve() {
    std::vector<int> primes;
    std::iota(spf, spf + MAXA, 0); // 初始化 spf[i] = i
    mu[1] = 1;
    for (int i = 2; i < MAXA; ++i) {
        if (spf[i] == i) { // i 是质数
            mu[i] = -1;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > spf[i] || 1LL * i * p >= MAXA) break;
            spf[i * p] = p;
            if (p == spf[i]) { // p 是 i 的最小质因子
                mu[i * p] = 0;
                break;
            } else { // p 比 i 的最小质因子还小
                mu[i * p] = -mu[i];
            }
        }
    }
}

// 预处理每个数的所有约数
void precompute_all_divisors() {
    for (int i = 1; i < MAXA; ++i) {
        for (int j = i; j < MAXA; j += i) {
            all_divisors[j].push_back(i);
        }
    }
}

// --- 查询辅助函数 ---

// 根据一个数 v，找出它的所有无平方因子约数
void get_sq_free_divs(int v) {
    p_factors_cache.clear();
    int temp = v;
    // 1. 找出所有质因子
    while (temp > 1) {
        int p = spf[temp];
        p_factors_cache.push_back(p);
        while (temp % p == 0) {
            temp /= p;
        }
    }

    // 2. 用质因子组合出所有无平方因子约数
    sq_free_divs_cache.clear();
    int k = p_factors_cache.size();
    sq_free_divs_cache.reserve(1 << k); // 预留空间
    for (int i = 0; i < (1 << k); ++i) {
        int d = 1;
        for (int j = 0; j < k; ++j) {
            if ((i >> j) & 1) { // 用二进制位来决定是否乘上这个质因子
                d *= p_factors_cache[j];
            }
        }
        sq_free_divs_cache.push_back(d);
    }
}

int main() {
    fast_io();

    // 预处理，喵~
    linear_sieve();
    precompute_all_divisors();

    std::cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
    }

    for (int k = 0; k < q; ++k) {
        int x;
        std::cin >> x;
        int v = a[x];

        get_sq_free_divs(v); // 找到 v 的无平方因子约数
        long long delta = 0;

        if (on_shelf[x]) {
            // --- 移除啤酒 ---
            // 1. 先更新状态：把 v 的贡献从 counts 中移除
            for (int d : all_divisors[v]) {
                counts[d]--;
            }
            on_shelf[x] = false;

            // 2. 计算 v 曾经的贡献值 delta
            for (int d : sq_free_divs_cache) {
                delta += mu[d] * counts[d];
            }
            // 3. 从总分中减去
            total_score -= delta;

        } else {
            // --- 添加啤酒 ---
            // 1. 先计算 v 能带来的新贡献 delta
            for (int d : sq_free_divs_cache) {
                delta += mu[d] * counts[d];
            }
            // 2. 加到总分里
            total_score += delta;

            // 3. 再更新状态：把 v 的信息加入 counts
            for (int d : all_divisors[v]) {
                counts[d]++;
            }
            on_shelf[x] = true;
        }
        std::cout << total_score << "\n";
    }

    return 0;
}

题目大意

解题思路

题解代码

相关知识点介绍

1. 莫比乌斯函数 (Möbius Function)

2. 容斥原理 (Principle of Inclusion-Exclusion)

3. 线性筛 (Linear Sieve)

题目大意 ​

解题思路 ​

题解代码 ​

相关知识点介绍 ​

1. 莫比乌斯函数 (Möbius Function) ​

2. 容斥原理 (Principle of Inclusion-Exclusion) ​

3. 线性筛 (Linear Sieve) ​

题目大意

解题思路

题解代码

相关知识点介绍

1. 莫比乌斯函数 (Möbius Function)

2. 容斥原理 (Principle of Inclusion-Exclusion)

3. 线性筛 (Linear Sieve)