Subscribed unsubscribe Subscribe Subscribe

0w1

CFR 547 C. Mike and Foam ( Mobius Inversion )

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

HR Hyperrectangle GCD ( Mobius Inversion )

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

Codechef COPRIME3 ( Mobius Inversion )

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解法: 和上方…