POJ 2720 Last Digits

Problem Description:
f(x) = 1, if x = 0
B ** f(x - 1), otherwise
Given B, I, and N, find the last N digits of f(I).

Constraints:

Solution:
We want to find .
For any , we can observe that in , we can always find some such that .
We will recursively compute the answer, i.e. from the most top value to the bottom.
Note that , and .
Since , we will keep track whether at some moment the power has exceeded . When such situation occurs, all later calculations only involve the second case, otherwise, honestly compute the first case without applying modulo.

Code:

#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cmath>

const int MAXB = 100;
const int MAXI = 100;
const int MAXN = 7;
const int MOD = 1e7;

int B, I, N;

int ten[MAXN + 1];
int i_phi[MAXI + 1]; // interesting phi's
int bp[MAXB + 1][25][MAXI + 1];
int dp[MAXB + 1][MAXI + 1][MAXI + 1];
int gp[MAXB + 1][MAXI + 1][MAXI + 1];

int phi(int x) {
  int r = x;
  for (int i = 2; i * i <= x; ++i) {
    if (x % i == 0) {
      r = r / i * (i - 1);
      while (x % i == 0) x /= i;
    }
  }
  if (x != 1) r = r / x * (x - 1);
  return r;
}

int mod_pow(int v, int p, int mi) {
  if (i_phi[mi] == 1) return 0;
  if (v == 1 || p == 0) return 1;
  int r = 1;
  for (int i = p; i; i &= i - 1) {
    r = 1LL * r * bp[v][__builtin_ctz(i)][mi] % i_phi[mi];
  }
  return r;
}

int int_pow(int v, int p) {
  int r = 1;
  while (p--) r *= v;
  return r;
}

void solve(int b, int p, int mi) {
  if (~dp[b][p][mi]) return;
  if (i_phi[mi] == 1) return dp[b][p][mi] = 0, void();
  if (b == 1 || p == 0) return dp[b][p][mi] = 1, void();
  solve(b, p - 1, mi + 1);
  int q;
  if (gp[b][p - 1][mi + 1]) {
    q = dp[b][p - 1][mi + 1] + i_phi[mi + 1];
    dp[b][p][mi] = mod_pow(b, q, mi);
    gp[b][p][mi] = 1;
  } else {
    q = dp[b][p - 1][mi + 1];
    if (log10(b) * q >= 7) {
      dp[b][p][mi] = mod_pow(b, q, mi);
      gp[b][p][mi] = 1;
    } else {
      dp[b][p][mi] = int_pow(b, q);
      gp[b][p][mi] = 0;
    }
  }
}

signed main() {
  for (int i = ten[0] = 1; i <= MAXN; ++i) {
    ten[i] = ten[i - 1] * 10;
  }
  i_phi[0] = MOD;
  for (int i = 1; i <= MAXI; ++i) {
    i_phi[i] = phi(i_phi[i - 1]);
  }
  for (int i = 2; i <= MAXB; ++i) {
    for (int j = 0; j + 1 < 25; ++j) {
      for (int k = 0; k <= MAXI; ++k) {
        if (j == 0) bp[i][j][k] = i % i_phi[k];
        bp[i][j + 1][k] = 1LL * bp[i][j][k] * bp[i][j][k] % i_phi[k];
      }
    }
  }
  std::memset(dp, 0xff, sizeof(dp));
  std::ios::sync_with_stdio(false);
  while (std::cin >> B >> I >> N) {
    solve(B, I, 0);
    int ans = dp[B][I][0] % ten[N];
    int d = 0;
    while (d < N && ans >= ten[d]) ++d;
    for (int i = 0; i + d < N; ++i) {
      std::cout << 0;
    }
    if (ans) std::cout << ans;
    std::cout << '\n';
  }
  return 0;
}