1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
| #include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <algorithm> #include <cmath> #include <cctype> #include <iostream> #include <iomanip> int table[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000 }; inline int pow(int x, int y) { if (y < 0) return -1; register int ans = 1; for (register int i = 0; i < y; i++) { ans *= x; if (ans >= table[7]) return -1; } return ans; } const int MAXN = 3000; typedef long long ll; int phi[MAXN + 10], prime[MAXN + 10], tot; bool vis[MAXN + 10]; int f[101][101], ans[101][101]; int getPhi(int x) { int ret = x; for (int i = 2; i * i <= x; i++) { if (x % i == 0) { ret = ret / i * (i - 1); for (; x % i == 0; x /= i); } } if (x != 1) { ret = ret / x * (x - 1); } return ret; } inline void init() { phi[1] = 1; for (register int i = 2; i <= MAXN; i++) { if (!vis[i]) prime[++tot] = i, phi[i] = i - 1; for (register int j = 1; j <= tot; j++) { if (i * prime[j] > MAXN) break; vis[i * prime[j]] = 1; if (i % prime[j] == 0) { phi[i * prime[j]] = phi[i] * prime[j]; break; } else phi[i * prime[j]] = phi[i] * (prime[j] - 1); } } memset(ans, -1, sizeof(ans)); for (register int i = 1; i < 101; i++) { f[i][0] = 1; for (register int j = 1; j < 101; j++) f[i][j] = pow(i, f[i][j - 1]); } } inline int modPow(ll x, int b, int mod) { register int ret = 1; for (; b; b >>= 1, x = x * x % mod) if (b & 1) ret = ret * x % mod; return ret; } inline int solve(int b, int x, int mod) { if (x == 0) return 1; if (mod == 1) return 0; if (f[b][x] < 0) { register int euler = getPhi(mod); return modPow(b, solve(b, x - 1, euler) + euler, mod); } else return f[b][x] % mod; } int main() { init(); int b, i, n, ans; char format[] = "%00d\n"; while (~scanf("%d", &b) && b) { scanf("%d%d", &i, &n); format[2] = char(n + '0'); if (::ans[b][i] == -1) { if (b == 1) ans = 1; else ans = solve(b, i, table[7]); ::ans[b][i] = ans; } ans = ::ans[b][i] % table[n]; printf(format, ans); } return 0; }
|