Problem - 547C - Codeforces題意： 給 N 個數字的數列 A。接著 Q 筆操作，每次將 A[ idx ] 取出 / 放入一個櫃子。求每次操作完，櫃子裡有多少無序對，其最大公因數為 1。資料規模： N, Q ≤ 2e5 max{ A } ≤ 5e5 TL: 2000 ms解法： 令 p 序列為當前櫃子裡的值…

https://www.hackerrank.com/challenges/hyperrectangle-gcd題意： 有 K 個箱子，裡面分別有 [ 1, N[ i ] ] 的數字。現在要從每個箱子里抽一個數字，求其最大公因數。問所有取法可以產生的最大公因數總和。資料規模： Constraints 1 2 1 p.s. T * nk * K 明…

https://www.codechef.com/problems/COPRIME3可以先看這個連結了解 Mobius Inversion 是什麼： A Dance with Mobius Function - Posts - Quora題意： 給 N 個數字的數列 A，問有多少對 ( i, j, k ) 滿足 i 資料規模： N ≤ 1e5 1 ≤ A[ i ] ≤ 1e6解法： 和上方…