問題
初始數列 A[i]=i (1≤i≤n)。操作：1) 查詢 [x,y] 中與 p 互質的數的和；2) 單點修改 A[pos]=val。操作數 ≤ 1000，n ≤ 4×10⁵。
核心：容斥原理計算 1..n 中與 p 互質的和
- 分解 p 的質因子：p = ∏ pᵢ。
- 不互質的數 = 能被至少一個 pᵢ 整除的數。利用容斥原理，枚舉質因子非空子集，符號交替，計算倍數和。
- 倍數和：項為 d = 子集乘積，個數 t = n/d，和 = d × t(t+1)/2。
- 互質和 = 總和 n(n+1)/2 - 不互質和。
處理修改操作
用 map 記錄所有修改過的位置及其當前值。查詢時：先用容斥算出原始區間 [x,y] 的互質和，再遍歷 map 中屬於 [x,y] 的修改點：若原值互質則減去，若新值互質則加上。修改操作直接更新 map。
工程細節
- 預處理 4×10⁵ 內所有數的質因子（線性篩），存入結構體數組。
- 容斥用 DFS 枚舉子集，深度 ≤ 質因子個數（最多 ~7），極快。
- 數據範圍需 64 位整數（long long）。
- 修改點判斷互質用 gcd(val, p)==1。
複雜度
預處理 O(N log log N)。單次查詢 O(2^ω(p) + M_log) ，ω(p) 為質因子數，M 為修改點數（≤1000）。完全滿足要求。
