「プロジェクトオイラー問４８」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問４８ - (2014/02/17 (月) 21:57:36) のソース

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2048


Problem 48 「自身のべき乗(self powers)」 †
次の式は, 1＾1 + 2^2 + 33 + ... + 10^10 = 10405071317 である.

では, 1^1 + 2^2 + 3^3 + ... + 1000^1000 の最後の10桁を求めよ.

解法
mod演算の中で計算すれば結構速いですね。


 modPow(_,0,1):-!.
 modPow(Pow,R,Result):-
 	R mod 2=:=1,
 	!,
 	R1 is R//2,
 	Pow1 is (Pow^2) mod 10^10,
 	modPow(Pow1,R1,Re),
 	Result is (Re*Pow) mod 10^10.
 modPow(Pow,R,Result):-
 	!,
  	R1 is R//2,
 	Pow1 is (Pow^2) mod 10^10,
 	modPow(Pow1,R1,Result).
 
 calc(1001,Sum,Sum):-!.
 calc(N,Sum,Result):-
 	!,
 	modPow(N,N,Add),
  	Sum1 is Sum+Add,
 	N1 is N+1,
 	calc(N1,Sum1,Result).
 main48:-
 	calc(1,0,Ans),
 	Ans1 is Ans mod 10^10,
 	write(Ans1).