fork download
  1. // BOJ 4862 - 마지막 자리
  2. #include <bits/stdc++.h>
  3. #define endl "\n"
  4.  
  5. using namespace std;
  6. using ll = long long;
  7. using ull = unsigned long long;
  8.  
  9. ll modpow(ll a, ll b, ll c) {
  10. ll ret = 1;
  11. while (b) {
  12. if (b & 1) ret = ret * a % c;
  13. b >>= 1;
  14. a = a * a % c;
  15. }
  16. return ret;
  17. }
  18.  
  19. ll phi(ll n) {
  20. ll result = n;
  21.  
  22. for (ll i = 2; i * i <= n; ++i) {
  23. if (n % i == 0) {
  24. result -= result / i;
  25. while (n % i == 0) n /= i;
  26. }
  27. }
  28.  
  29. if (n > 1)
  30. result -= result / n;
  31.  
  32. return result;
  33. }
  34.  
  35. ll naive(const ll b, const ll x, const ll m) {
  36. if (x == 0) return 1;
  37. else return modpow(b, naive(b, x - 1, m), m);
  38. }
  39.  
  40. ll f(const ll b, const ll x, const ll m) {
  41. if (m == 1) return 1; // 대신 마지막에 f(b, x, m) % m을 해줘야 함
  42. if (x == 0) return 1;
  43. if (x <= 5) return naive(b, x, m);
  44.  
  45. // a^p = a^(p mod phi(m) + phi(m)) mod m을 이용해 구할 수 있다.
  46. const ll p = phi(m);
  47. return modpow(b, f(b, x - 1, p) + p, m);
  48. }
  49.  
  50. int main() {
  51. ios_base::sync_with_stdio(false);
  52. cin.tie(nullptr);
  53. cout.tie(nullptr);
  54.  
  55. while (true) {
  56. int b, i, n;
  57. cin >> b;
  58. if (b == 0) break;
  59. cin >> i >> n;
  60.  
  61. ll m = 1;
  62. for (int j = 0; j < n; j++) {
  63. m *= 10;
  64. }
  65.  
  66. cout << setw(n) << setfill('0') << f(b, i, m) % m << endl;
  67. }
  68.  
  69. return 0;
  70. }
  71.  
Success #stdin #stdout 0.01s 5320KB
stdin
2
12
7
0
stdout
8948736