FAQ
RSS
|
|
ツイート
|
各桁の和を求めよ(1)
hiyoko
解答判定ワード
回答募集は終了しました。
hiyoko
2進法・・・そうですね.
関係ないとは決していえないですが,とりあえず, 2^127-1 という数自体はある程度は意味はあります. 2^127-1 という数のどんな性質に何の意味があるのか それを探ること自体がすでに問題だとおもいます  ただ, 2^k-1 の形であること自体に大きな意味はないです. 2^k-1 という数だから,超高速で素数判定する方法(LLT法)が存在する, ということはあります(そこの部分については2進法は大いに関係あり) ただ, 仮に 2^127-1 が素数だとわかったとして, その性質だけから,ただちに各桁の和を得る方法は私は知らないです. 素数という条件が必要だとするなら,2^127-1という数からはそれだけに飽き足らずもっと情報を引き出す必要があるということです(想定解だと) 
hiyoko
参考にされたサイトの情報はわたしのみたところ正しいようですが,
伊藤那由多さんの答え自体は不正解の値のようです. ご存知だとはおもいますが, (9/2)*(循環節の長さ) になるはずですよね 詳しくは後述しますが. (一般には,pが素数だろうが,p-1は循環節の長さになるとは限りません.例:p=37) この問題は循環節の長さを求めることが必要です. 想定解では,pが素数であること,および, 循環節の長さが偶数であることから, 「循環節の長さをuとすると, 9u/2 が答え」であるという, midyの定理の類するものが初等数論的考察からわかるので, それを用いて計算するという方法です. ただ循環節の長さはどうやって計算するのか というところもポイントとなります. 循環節の長さは 10^t≡1(mod p)を満たす最小の正の整数tと一致するわけですがそれはどうやって計算するのかということです. tを1,2,3..,とあてはめていくという方法は今回のケースでは計算量的に不可能ですから,すこし工夫する必要があります. 力技でやられた人が正解しているようですが, おそらくなんらかの工夫をしているはずなんですね. 
hiyoko
正解です！
そうですね.特定のいくつかのxに対しては,10^xをmod pで計算することはバイナリ法により可能ということ,および,p-1の素因数分解を利用する(コメントに書いてくれたとおりの)ということを組み合わせることで解けますね
|
算数・数学クイズ
算数・数学クイズ
計算
問題へジャンプ