hiyoko
参考にされたサイトの情報はわたしのみたところ正しいようですが,
伊藤那由多さんの答え自体は不正解の値のようです.
ご存知だとはおもいますが,
(9/2)*(循環節の長さ) になるはずですよね 詳しくは後述しますが.
(一般には,pが素数だろうが,p-1は循環節の長さになるとは限りません.例:p=37)
この問題は循環節の長さを求めることが必要です.
想定解では,pが素数であること,および,
循環節の長さが偶数であることから,
「循環節の長さをuとすると, 9u/2 が答え」であるという,
midyの定理の類するものが初等数論的考察からわかるので,
それを用いて計算するという方法です.
ただ循環節の長さはどうやって計算するのか
というところもポイントとなります.
循環節の長さは 10^t≡1(mod p)を満たす最小の正の整数tと一致するわけですがそれはどうやって計算するのかということです.
tを1,2,3..,とあてはめていくという方法は今回のケースでは計算量的に不可能ですから,すこし工夫する必要があります.
力技でやられた人が正解しているようですが,
おそらくなんらかの工夫をしているはずなんですね.
