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

Google Code Jam

B : バクテリアの増殖

  • この問題を解くための基本アイディアとして
    • n時間後のバクテリア数を x(n) とする
    • ( x(n)^x(n) )%C = ( (x(n)%C)^x(n) )%C である
    • ((x(n)%C)^p)%C = 0 となるpがなければ、x(n)%C のべき乗は値が循環する
    • その循環の長さを y とすると ( (x(n)%C)^x(n) )%C = ( (x(n)%C)^(y+x(n)%y) )%C
      • 何乗かしてからサイクルに入る場合もあるので、1周分以上は計算する
  • まとめると、x(n+1)%C を求めるには x(n)%C、サイクル長y、x(n)%y が必要
    • x(n)を1〜Cで割った余りを求めておけば、x(n+1)を1〜Cで割った余りが求められる
    • サイクル長はオイラーのφ関数によって求めておける
  • x(1)を1〜Cで割った余りは単純に計算して求めておける
  • これを使って、上記によりx(2), x(3),... について求めていけば良い
  • また、2^10 > 1000 なので、A^10がCで割り切れなければ答えは0にならない

書いてみたコード

#include <iostream>

using namespace std;

int cycle[1001];

int modPow(int A, int p, int C){
    if(p==0) return 1;
    int res = modPow(A, p/2, C);
    res = (res*res)%C;
    if(p%2 == 1) res = (res*A)%C;
    return res;
}

int solveLarge(int A, int B, int C){
    // 答えが0にならないかチェック
    int t = modPow(A, 10, C);
    if(B >= 2 && t == 0){
        if(A == 2 && B == 2 && C > 256) return 256;
        return 0;
    }

    int res[2][1001];
    for(int i=1;i<=C;i++)
        res[0][i] = modPow(A, A, i);

    int cur = 0, next = 1;
    for(int i=2;i<=B;i++){
        res[next][1] = 0;
        for(int j=2;j<=C;j++){
            int c = cycle[j];
            int p = res[cur][c];
            res[next][j] = modPow(res[cur][j], c+p, j);
        }
        swap(cur, next);
    }
    return res[cur][C];
}

int main(){
    int TEST; cin >> TEST;
    // オイラーのφ関数で周期を求めておく
    for(int i=1;i<=1000;i++) cycle[i] = i;
    for(int i=2;i<=1000;i++){
        if(cycle[i] != i) continue;
        for(int j=i;j<=1000;j+=i)
            cycle[j] = cycle[j]/i*(i-1);
    }

    for(int test=1;test<=TEST;test++){
        int A, B, C; cin >> A >> B >> C;
        printf("Case #%d: %d\n", test, solveLarge(A, B, C));
    }
}