プロジェクトオイラー 問９７

プロジェクトオイラーの問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問９７「大きな非メルセンヌ素数」
100万桁を超える初めての素数は1999年に発見された. これはメルセンヌ素数であり, 26972593-1 である. 実際, 2,098,960桁ある. 
それ以降も, より多くの桁になるメルセンヌ素数 (2p-1の形の数) が他にも発見されている.

しかし, 2004年に, 非常に大きな非メルセンヌ素数が発見された. 
これは2,357,207桁の数であり, 28433×27830457+1である.

この素数の末尾10桁を答えよ.






注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の回答例は以下の通りです。

def f(a, n, p, b, m):
	k, t, c = n, 10**m, 1
	for s in str(p)[::-1]:
		c *= k**(int(s))%t
		k = k**10%t
	return (a*c+b)%t

def f2(a, p, b, m): return ((a<<p)+b)%(10**m)

#（ａ×（ｎのｐ乗）＋ｂ）の末尾m桁を返す
a, n, p ,b ,m =28433, 2, 7830457, 1,10
s = f(a, n, p ,b ,m)
print s

#（ａ×（２のｐ乗）＋ｂ）の末尾m桁を返す
a, p ,b ,m =28433, 7830457, 1,10
s = f2(a, p ,b ,m)
print s

１．関数f(a, n, p, b, m)
・a×np＋b　の末尾m桁を返します。

・for s in str(p)[::-1]:
　数値pをstr関数で文字型にして、文字のスライス機能の[開始:終了:刻み]での刻みを-1にすることで右から１文字ずつ、つまり１の位の数字から順に１つずつ取り出し、ループ変数sに設定します。

・c *= k**(int(s))%t
　k = k**10%t
　変数kは、ループ変数sの桁位置に相当するnの累乗値を設定します。
　初期値はnで、ループが回るにつれ、nの10回累乗、100回累乗、...と直前の累乗値を10回ずつ累乗していきます。
　変数cに、kのs乗をかけて、ためていきます。
　例えば、
　2の345乗ならば、(2の5乗) x ((2の10乗))の4乗) x ((2の100乗)の3乗)です。
　このときの「2の10乗」「2の100乗」が変数kで、各桁の数字が変数sです。

２．（別解）関数f2(a, p ,b ,m)
・a×2p＋b　の末尾m桁を返します。
　関数の中の累乗計算を、2の累乗に固定します。

・a<<p
　数値aをpビット左にシフトすることで、2進数でp桁繰り上がります。
　これは、数値aに対して2をp回かけることと同じです。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
8739992577