Back to : ps-problems
Contents

좜처 : 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}))$ 보닀도 훨씬 λŠλ ΈμŠ΅λ‹ˆλ‹€. κ°„μ‹ νžˆ μ‹œκ°„ μ œν•œμ„ 톡과할 수 μžˆμ—ˆμŠ΅λ‹ˆλ‹€. :(