Google Code Jam Japan 2011 決勝 B. バクテリアの増殖 (Small)

バクテリアの増殖

SmallではBは2以下、1回目は普通に計算するとバクテリアの個数は10進数で高々3000桁。A^A mod CはO(log A)で計算できる。参考。Pythonならpow関数に任せれば良い。

def solve(A,B,C):
    if B==1:
        return A**A%C
    else:
        A = A**A
        return pow(A,A,C)

for t in xrange(input()):
    A,B,C = map(int,raw_input().split())
    ans = solve(A,B,C)
    print "Case #%s: %s" % (t+1,ans)