コンテンツにスキップ

0150: 循環小数の循環節

問題

有理数の十進小数展開は、有限桁で終わるか、ある桁から先が同じ数字列の繰り返しになります。 この繰り返しの最小単位を循環節（repetend）と呼びます。 例えば \(1/7 = 0.\overline{142857}\) の循環節は 142857 であり、\(1/6 = 0.1\overline{6}\) の循環節は 6 です。

関数 repetend(p, q) を実装してください。 分数 \(p/q\) の小数展開の循環節を、循環が始まる位置から1周期分の数字列（str）として返します。 小数展開が有限桁で終わる場合は空文字列 '' を返します。 整数部分は循環節に関係しないため、repetend(22, 7) は repetend(1, 7) と同じ結果になります。

制約

  • p は 0 以上の整数、q は 1 以上の整数です。
  • この条件を満たさない引数には ValueError を送出します。
  • q は最大 \(10^6\) 程度を想定します。
  • 整数演算のみで求めます。浮動小数点演算は誤差のため使えません。

例

>>> repetend(1, 7)
'142857'
>>> repetend(1, 6)
'6'
>>> repetend(3, 8)
''
>>> repetend(22, 7)
'142857'
>>> repetend(1, 12)
'3'
>>> len(repetend(1, 97))
96
>>> repetend(1, 0)
Traceback (most recent call last):
  ...
ValueError: p must be >= 0 and q must be >= 1

発展

q が 10 と互いに素な素数のとき、循環節の長さは \(q\) を法とする 10 の乗法的位数（\(10^k \equiv 1 \pmod q\) となる最小の \(k \ge 1\)）に一致します。 小数展開を作らずにこの位数だけを求める関数 repetend_length(q) を書き、len(repetend(1, q)) と一致することを確かめてください。

参考