Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
(ns repeating-decimal)
(defn repeating-decimal [n]
(loop [rem 1 rems #{} divs [] i 0]
(let [div (int (/ (* rem 10) n))
rem (mod (* rem 10) n)]
(if (and (not= rem 0) (contains? rems rem))
[n divs]
(when (not= rem 0)
(recur rem (conj rems rem) (conj divs div) (inc i)))))))
(comment
(repeating-decimal 7)
(repeating-decimal 11)
(repeating-decimal 12)
(repeating-decimal 97)
)
(defn solve [n]
(loop [i n, m 0, divs []]
(let [l (count divs)]
(if (> i l)
(let [divs' (repeating-decimal i)
l' (count divs')]
(if (> l' l)
(recur (dec i) i divs')
(recur (dec i) m divs)))
[m divs]))))
;; (solve 100000)
@athos

This comment has been minimized.

Copy link
Owner Author

commented Sep 4, 2017

  • 1/nの循環節の長さはnを超えない
    • 同じ剰余が現れたら循環 ⇒ ありうる剰余は 0n-1n通り
  • つまり、たとえば10000以下の数n1/n10000以上の長さの循環節を持つことはない
  • この性質を利用すれば、100000, 99999, 99998, ..., その時点の循環節の最大長 の範囲の数だけを探索すればいい
    • それ以上小さい値をチェックしても、より長い循環節をもつ数がないことが保証されるため
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.