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).
最終更新:2014年02月17日 21:57