Codeforces 109B：數論 + 素因子分解 判斷衝突

題目描述

有 n 個數（1~n），初始均未激活。操作：

• + x：激活 x。若 x 已激活，輸出 "Already on"。若存在已激活數 y 使 gcd(x,y) > 1，輸出 "Conflict with y"。否則激活並輸出 "Success"。
• - x：停用 x。若未激活，輸出 "Already off"，否則停用並輸出 "Success"。

n, m ≤ 1e5。

核心觀察

兩數不互質 ⇔ 存在公共質因數。維護每個質因數是否被某激活數佔用即可。

算法流程

1. 預處理：線性篩法計算 1~n 每個數的質因數集合 vec[i]。
2. 數組 vis[p] 記錄佔用質因數 p 的激活數（0 表示未佔用）。
3. 數組 active[x] 記錄 x 是否激活。
4. 操作 + x：
   • 若 active[x] → "Already on"。
   • 遍歷 vec[x]，若某 p 有 vis[p] != 0 → "Conflict with vis[p]"。
   • 否則置 active[x]=1，對所有 p ∈ vec[x] 置 vis[p]=x，輸出 "Success"。
5. 操作 - x：
   • 若 !active[x] → "Already off"。
   • 置 active[x]=0，對所有 p ∈ vec[x] 置 vis[p]=0，輸出 "Success"。

C++ 代碼實現

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

const int MAXN = 100010;
vector primeFactors[MAXN];
int vis[MAXN] = {0};      // 質因數 -> 佔用者
bool active[MAXN] = {0};  // 數是否激活

void sieve() {
    for (int i = 2; i < MAXN; ++i) {
        if (primeFactors[i].empty()) { // i 是質數
            for (int j = i; j < MAXN; j += i)
                primeFactors[j].push_back(i);
        }
    }
}

int main() {
    sieve();
    int n, m; 
    while (scanf("%d%d", &n, &m) == 2) {
        fill(vis, vis + MAXN, 0);
        fill(active, active + MAXN, false);
        while (m--) {
            char op; int x;
            scanf(" %c%d", &op, &x);
            if (op == '+') {
                if (active[x]) { puts("Already on"); continue; }
                int conflict = 0;
                for (int p : primeFactors[x]) 
                    if (vis[p]) { conflict = vis[p]; break; }
                if (conflict) printf("Conflict with %d\n", conflict);
                else {
                    active[x] = true;
                    for (int p : primeFactors[x]) vis[p] = x;
                    puts("Success");
                }
            } else { // '-'
                if (!active[x]) { puts("Already off"); continue; }
                active[x] = false;
                for (int p : primeFactors[x]) vis[p] = 0;
                puts("Success");
            }
        }
    }
    return 0;
}

複雜度

• 預處理：O(n log log n)。
• 每操作：O(質因數個數) ≤ O(log n)。
• 總時間：O((n+m) log n)，空間：O(n log n) 存儲質因數列表。