問題大意
序列長度 n ≤ 2×10⁵，m 次查詢 [l,r]。問區間中有多少個數，與區間內**所有**數互質（即該數的質因子在區間內不出現在其他數中）。
核心轉化
一個數 `a[i]` 在區間 [l,r] 中「好」⇔ 它的所有質因子在 [l,r] 中**只出現在 i 這一個位置**。即對每個質因子 p，`i` 是 [l,r] 中唯一被 p 整除的位置。
預處理左右最近同質因子位置
- 線性篩預計算每個數的質因子（不含 1）
- 左到右掃描：`l[i]` = 區間 [1,i-1] 中與 `a[i]` 有公共質因子的**最右**位置（無則 0）
- 右到左掃描：`r[i]` = 區間 [i+1,n] 中與 `a[i]` 有公共質因子的**最左**位置（無則 n+1）
離線查詢 + 樹狀數組
- 查詢按左端點 l 降序排序
- 維護樹狀數組：位置 i 為 1 表示 `a[i]` 當前「好」（即其質因子在當前考慮範圍內唯一）
- 初始：`l[i]==0` 的位置置 1，並在 `r[i]` 處標記 -1（差分思想）
- 遞減 l：將 `l[j] == l` 的位置 j 從「壞」變「好」（加 1），同時在 `r[j]` 標記 -1
- 查詢 [l,r] 答案 = 前綴和查詢 `sum(l) - sum(r+1)`
複雜度
預處理 O(n log log MAX + n × 質因子數)，查詢 O((n+m) log n)。完美通過限制。
