循環小数の途中の桁を求める問題として以下の例題を考えます。
【例題】分母が$10^6$以下の素数の単位分数（分子が１のもの）で、循環節が最長の循環小数の小数以下の桁$N=10^5$から10桁を求めよ
最長の循環小数の分母の素数
これに関してはProject Euler】Problem 26: 循環小数で解説しましたので参考にしてください。分母の素数の答えは$999983$になります。この時、循環節の長さは1引いた$999982$となるのでそれを全部求めるのは、かなり大変です。
求める部分を整数部に持ってくる
小数以下$N$桁から10桁を求めるので、分子を$10^{(N+10)}$倍すれば求める部分が整数部に出て来ます。それを$10^{10}$で割った余りが求める数となりますが、このやり方だと$10^5$桁の不必要な部分を求めているので非効率です。
N, w = 10**5, 10
d = 999983
print(f"1/{d}= 小数以下{N}桁から{w}桁は {(10**(N+w)//d)%10**w:0{w}}")
# 1/999983: 小数以下100000桁から10桁は 2937029929
求める部分を小数部の先頭に持ってくる
そこでまず考え方を変えて求める部分を小数部の先頭に持って来ます。すなわち分子を$10^{N}$倍します。これを$d$で割るのですが、結果の整数部は要らないので、先に分子を$d$で割った余りを求めてから$d$で割ります。式としては以下のようになります。
N = 10^5 \\
d = 999983 として\\ \\
X = 小数部(10^N / d) \\
= (10^N \pmod d) / d
これをプログラムにします。最終的に$10^{10}$倍して整数を取り出します。この方法だと分子は高々$d$までなので、割り算の計算量は抑えられます。
N, w = 10**5, 10
d = 999983
print(f"1/{d}: 小数以下{N}桁から{w}桁は {int(pow(10,N,d)/d*10**w):0{w}}")
# 1/999983: 小数以下100000桁から10桁は 2937029929
この考え方は以下のProject Eulerの問題を解くのに役に立ちます。
- Problem 731: A Stoneham Number
- Problem 820: Nth digit of Reciprocals
(開発環境：Google Colab)