（转载）有关反演和gcd

tips :

积性函数 F (n) = Π F (p_i^ai )

若F (n), G (n)是积性函数则

F (n) * G (n)

Σ_{d | n}F (n)

是积性函数

n = Σ_{d | n}φ (d)

1 = Σ_{d | n}μ (d)

Σ_{gcd (i, n) = 1} i = n * φ (n) / 2

Problem1

F (n) = Σ_{1<= i <= n} gcd(i, n), n <= 1000000

Sol

枚举结果

F (n) = Σ_{d | n} d * Σ_{gcd (i, n) = d} 1

F (n) = Σ_{d | n} d * Σ_{gcd (i / d, n / d) = 1} 1

F (n) = Σ_{d | n} d * Σ_{gcd (i / d, n / d) = 1} 1

F (n) = Σ_{d | n} d * φ (n / d)

单次计算O (sqrt N)

筛法O (N)

Problem 2

F (n) = Σ_{1<= i <= n} gcd (i, n), n <= 2147483647 (POJ longge's problem)

Sol

由P1可知F (n)是积性函数因此考虑计算F (p^k)

由P1 易知

F (p^k) = p * F (p^{k - 1}) + (p - 1)p^{k - 1}

单个F(n)可以O (sqrt N)时间有他的质因子分解计算得到

Problem 3

F (n) = Σ_{1<= i <= n} lcm(i, n), n <= 1000000 (SPOJ LCMSUM)

显而易见的变形

F (n) = Σ_{1<= i <= n} i * n / gcd (i, n)

F (n) =Σ_{d | n} Σ_{gcd (i, n) = d} i * n / d

F (n) =Σ_{d | n}n / d * Σ_{gcd (i, n) = d} i

F (n) =Σ_{d | n}n / d * Σ_{gcd (i / d, n / d) = 1}i

F (n) =Σ_{d | n}n / d * d * Σ_{gcd (i / d, n / d) = 1}i / d

令j = i / d

F (n) =Σ_{d | n}n * Σ_{gcd (j, n / d) = 1 j}

由Σ_{gcd (i, n) = 1} i = n * φ (n) / 2

F (n) =Σ_{d | n}n * (n / d) * φ (n / d) / 2

F (n) =n * Σ_{d | n}(n / d) * φ (n / d) / 2

F (n) =n / 2 * Σ_{d | n}d * φ (d)

筛出 Σ_{d | n}d * φ (d) O (N)-O(1)

Problem 4

F (n) = Σ_{1<= i <= n} Σ_{1<= j <= n} gcd (i, j) n <= 1000000 (SPOJ GCDEX)

Sol

G (n) = Σ_{d | n} d * φ (n / d)

F (n) = Σ_{1<= i <= n}G (i)

筛出G (i) 前缀和

Problem 5

求F (n, m) = [n / d] * [m / d]

Sol

研究退化情况 m = 1 F (n) = [n / d]

共有sqrt n种不同取值

F (n, m) = [n / d] * [m / d]

共有sqrt n + sqrt m种不同取值归并这两种取值

Problem 6

多组询问n, m 求F (n, m) = Σ_{1<= i <= n} Σ_{1<= j <= m} gcd (i, j)

Sol

F (n, m) = Σ_{1<= i <= n} Σ_{1<= j <= m}Σ_{d | gcd (i, j)} φ (d)

F (n, m) = Σ _d φ (d) Σ_{1<= i <= n d | i} Σ_{1<= j <= m d | j}1

F (n, m) = Σ _d φ (d) * [n / d] * [m / d]

可以经P5解决

Problem 6

多组询问n, m 求F (n, m) = Σ_{1<= i <= n} Σ_{1<= j <= m} _{gcd (i, j) = 1}1

Sol

F (n, m) = Σ_{1<= i <= n} Σ_{1<= j <= m}Σ_{d | gcd (i, j)} μ (d)

F (n, m) = Σ _d μ (d) Σ_{1<= i <= n d | i} Σ_{1<= j <= m d | j}1

F (n, m) = Σ _d μ (d) * [n / d] * [m / d]

可以经P5解决

Problem 7

F (n, m) = Σ1<= i <= n Σ1<= j <= m Σ _{gcd (i, j) <- prime} 1 (BZOJ YY的GCD)

Sol

F (n, m) = Σ1<= i <= n Σ1<= j <= m Σ _{gcd (i, j) <- prime} 1

F (n, m) = Σ1<= i <= n Σ1<= j <= m Σ _{p <- prime} _{gcd (i, j) = p} 1

F (n, m) = Σ _{p <- prime}Σ1<= i <= n Σ1<= j <= m _{gcd (i, j) = p} 1

F (n, m) = Σ _{p <- prime}Σ1<= i <= n / p Σ1<= j <= m / p gcd (n / p, m / p) = 1 1

可以经P6解决

巴特西

（转载）有关反演和gcd

最新文章

热门文章