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;
}