java - 2の累乗の最後の桁を取得する方法

Question

2^1001の最後の100桁を取得する必要がある問題に取り組んでいます。ソリューションはJavaであり、BigIntegerを使用せず、intまたはLongのみを使用する必要があります。今のところ、100桁を処理するクラスを作成すると思います。だから私の質問は、100桁の数値を取得するためにintまたはlongを使用してオーバーフローを処理する別の方法があるかどうかです。

全てに感謝。

Answer 1

編集：モジュロ演算子で10の2乗でオフになりました（おっと）

2 ^ 1001の最後の100桁は、数値2 ^ 1001（mod 10 ^ 100）です。

2 ^ 1001（mod 10 ^ 100）= 2 *（2 ^ 1000（mod 10 ^ 100））（mod 10 ^ 100）であることに注意してください。

モジュロのプロパティを調べます：http：//www.math.okstate.edu/~wrightd/crypt/lecnotes/node17.html

これは99％の数学の問題、1％のプログラミングの問題です。:)

ただし、このアプローチでは、10 ^ 100はintまたはlongに収まらないため、整数だけを使用することはできません。

ただし、これを使用して、たとえば2 ^ 1001の最後の10桁を検索し、次に別のルーチンを使用して次の10桁を検索するなど、各ルーチンがこの機能を使用する場合があります...

Answer 2

これを行う最も速い方法（コーディングに関して）は、100個の整数の配列を作成し、1桁目から開始して、すべての桁を2倍にする関数を作成することです。必ず10のモジュラスを取り、必要に応じて1を繰り越してください。100桁目は、キャリーオーバーを排除するだけです。1001回実行すれば完了です。