Google Code Jam Japan 2011 本戦 B. バクテリアの増殖(small)

B : バクテリアの増殖

• 本戦では、smallでも多倍長がいるなぁと思って諦めたのですが…。

• 多倍長で計算すれば良いらしかったです。これは目からウロコでした。
• 勉強がてらpythonとjavaで書いてみました。
  • こうしてみるとpythonのお手軽感ぱない

書いてみたコードたち

• Java版

import java.util.*;
import java.math.*;

public class B{
    private static String solveSmall(BigInteger A, int B, BigInteger C){
        A = A.pow(A.intValue());
        if(B==1) return A.mod(C).toString();
        return A.modPow(A, C).toString();
    }
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int testNum = sc.nextInt();
        for(int i=1;i<=testNum;i++){
            BigInteger A = new BigInteger(sc.next());
            int B = sc.nextInt();
            BigInteger C = new BigInteger(sc.next());
            System.out.println("Case #" + i +": " + solveSmall(A, B, C));
        }
    }
}

• Python版

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

def solve():
    test = int(raw_input())
    for i in range(test):
        A, B, C = map(int, raw_input().split())
        print "Case #%d: %d" % ((i+1), solveSmall(A, B, C))

solve()