BOJ 15744, USACO 2018 Feb P3 Cow Gymnasts
μΆμ² : USACO 2018 February Platinum Problem 3 - Cow Gymnasts (BOJ 15744)
λμ΄λ : solved.ac Diamond 3
λ¬Έμ λ§ν¬
νμ΄ : κ΄μ°°
DHdroidκ° βμ¬λ°λ λ¬Έμ β λΌλ©΄μ λ€κ³ μμ΅λλ€. λλ¦ μ¬λ°κ² νμλλ° νλ°μ μ’ νννμ΅λλ€.
- λ¨Όμ , $N$κ°μ μ리λ₯Ό ν΅νμ΄ μ΅μκ°μ΄ $m$ μ΄λΌκ³ νκ³ , κ·Έ μ΅μκ°μ΄ μλ μ리λ₯Ό $k$λ²μ΄λΌκ³ ν©μλ€.
- $k - 1, k - 2, \dots k - m + 1$ λ² κΉμ§λ μ΄μ© μ μμ΄ $k$λ²μ Contributeν©λλ€.
- $k-m$λ²μ $k$λ²μ Contributeν΄μλ μ λλ―λ‘, κ°μ΄ μ νν $m$μ΄μ¬μΌ ν©λλ€.
- μ΄μ κ°μ λ
Όμ¦μ κ·λ©μ μΌλ‘ λ°λ³΅νλ©΄, λ€μ 쑰건μ λ§μ‘±νλ μ‘°ν©μ΄ βμ±κ³΅νλ μ‘°ν©β μμ μ μ μμ΅λλ€.
- λ¨Όμ μ΅μκ° $m$μ λν΄ μ£ΌκΈ° $\gcd(m, N)$ μ κ°κ³ ,
- κ° μ£ΌκΈ° λ΄μμμ κ°μ $m$ λλ $m+1$ μ΄μ΄μΌ ν©λλ€.
- λ°λΌμ, λ€μ μμ κ³μ°νλ κ²μΌλ‘ λλ©λλ€. \(1 + \sum_{i = 1}^{N - 1} \left(2^{\gcd(i, N)} - 1\right)\) μ΄ κ΄μ°°μ νλ κ²κΉμ§λ§μ΄μμΌλ©΄ μλ§λ νλν°λ μ λμ λ¬Έμ μμ κ²μ λλ€.
νμ΄ : μκ° λ³΅μ‘λ μ€μ΄κΈ°
$N = 10^{12}$ μ΄κΈ° λλ¬Έμ, μ΄ μμ μκ° λ΄μ λ¨μνκ²λ κ³μ°ν μ μμ΅λλ€.
μμ μ‘λ€ν λΆλΆμ λΌκ³ $\sum_{i = 1}^{N} 2^{\gcd(i, N)}$ μ λΉ λ₯΄κ² κ³μ°νλ λ°©λ²μ λν΄ μκ°ν΄ λ³΄κ² μ΅λλ€.
λ¨Όμ , $\gcd(i, N) = g$ μΈ $i \leq N$μ κ°μλ₯Ό λΉ λ₯΄κ² μ μ μμ΅λλ€.
- $i$λ $g$μ λ°°μμ¬μΌ νλ―λ‘ $i = gk$ λΌκ³ μ°λ©΄, $\gcd(k, N/g)$ μ΄ 1μ΄μ΄μΌ νλ©°
- $k < N / g$ μ¬μΌ ν©λλ€.
- λ°λΌμ, μ΄λ¬ν $k$λ μ νν $\phi(N / g)$ κ° μκ³ , λ€μ μμ κ³μ°νλ©΄ λ©λλ€. \(\sum_{g \di N} 2^g \phi(N / g)\)
- $g \di N$ μ λͺ¨λ ꡬνλ κ²μ $O(\sqrt{N})$ μκ°μ΄ 걸리며, $g$κ° λͺ κ° μλμ§λ μ νν μ°κΈ° λ§€μ° μ΄λ ΅μ΅λλ€.
- λ€λ§, PSμμ μΌλ°μ μΌλ‘ μ°λ λ°μ΄λλ $O(n^{1/3})$ μ λλ€. μ¬λ°λ μ¬μ€μ, μ΄ λ°μ΄λλ μνμ μΌλ‘ μ°Ύμ λ°μ΄λκ° μλλΌ, $10^{9}$ κΉμ§μ μλ€ μ€ μ½μκ° κ°μ₯ λ§μ μκ° 1,344κ°, $10^{18}$ κΉμ§μ μλ€ μ€ κ°μ₯ λ§μ μκ° 103,680κ°μ μ½μλ₯Ό κ°κΈ° λλ¬Έμ λμΆ© μ λ§νΌ μ‘μΌλ©΄ λλ€λ κ²μ΄ μλ €μ Έ μλ€λ μ μ λλ€.
- $O(n^{1/3})$ κ°μ μ½μ κ°κ° $\phi(g)$ λ₯Ό ꡬνλ μκ°μ μ‘°κΈ λΉ‘λΉ‘ν©λλ€. ꡬ체μ μΌλ‘λ κ°λΉ $O(n^{1/2})$ μκ°μΈλ°
- μ€μ λ‘λ $g$λ€ μ€ μλΉμκ° $N$μ λΉν΄ λ§μ΄ μκΈ° λλ¬Έμ, $O(n^{1/3})$κ°μ μ½μμ λν΄ κ°κ° $\phi$ν¨μλ₯Ό ꡬνλ νμ΄λ μκ° μ νμ ν΅κ³Όν©λλ€.
- λ μ΅μ ννλ λ°©λ²μ, $\phi$ ν¨μλ κ·Έ μμ μμΈμλΆν΄ ννμ μν΄ μ ν΄μ§λ©°, $N$μ μμΈμλ λ§μμΌ μμ κ° μ μ΄λΌλ μ μ λλ€.
- κ°κ°μ $g \di N$ μ $N$μ μμΈμμ λΆλΆμ§ν©μ κ°κΈ° λλ¬Έμ, $p_1^{e_1} p_2^{e_2} p_3^{e_3}\dots$ μ λν΄ κ° μμΈμμ κ°μλ₯Ό iterateνλ©΄ λΉ λ₯΄κ² ꡬν μ μμ΅λλ€.
- μ μ§λ©΄ $O(n^{1/2} \log n)$ μ ꡬν μ μλ€κ³ ν©λλ€.
νμ΄ : λ κ³ ν΅λ°κΈ°
- μ λ μ μμΌλ‘ ν΅κ³Όν μμ μ΄ μμκΈ° λλ¬Έμ, λκ° μλ‘μ΄ μμ΄λμ΄λ₯Ό μ°ΎμμΌ νλ€κ³ μκ°νμ΅λλ€.
- Identity function $\iota$, Mobius function $\mu$ μ λν΄, $\phi = \mu * \iota$ μμ΄ μλ €μ Έ μμ΅λλ€. (λ리ν΄λ ν©μ±κ³±)
- $f(n) = 2^n$ μ $p$ ν¨μλΌκ³ νλ©΄, μ°λ¦¬μ λ¬Έμ λ $p * \phi$ μ κ°μ ꡬνλ κ²μ΄λ―λ‘, $p * \mu * \iota$ λ₯Ό ꡬνλ κ²μ΄κ³
- λ€μ μ΄λ₯Ό $\mu * (p * \iota)$ λ‘ λ°κΎΈμ΄ κ³μ°ν μ μμ΅λλ€.
μ²μ°Ένκ²λ, $\mu$λ₯Ό κ³μ°νκΈ° μν΄ ν¬ν¨-λ°°μ μ μ리λ₯Ό μ΄μ©ν΄μΌ νκΈ° λλ¬Έμ μκ° λ³΅μ‘λλ μ ν μ€μ΄λ€μ§ μκ³ $\log$ νμ΄ νλ λ λΆμ΅λλ€ (λ«ΌλΉμ°μ€ ν¨μμ κ°μ λͺ¨λ κ³μ°νλκ² μλλΌμ, map κ°μ μλ£κ΅¬μ‘°λ₯Ό μ΄μ©ν΄μΌ νκΈ° λλ¬Έ. μ¬μ§μ΄ κ²°κ³Όμ μΌλ‘ μ΄ νμ΄λ μ νμ΄μ $O(n^{5/6}))$ 보λ€λ ν¨μ¬ λλ Έμ΅λλ€. κ°μ ν μκ° μ νμ ν΅κ³Όν μ μμμ΅λλ€. :(