※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。



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).