题目188：数字的超幂

欧拉计划

The hyperexponentiation of a number

he hyperexponentiation or tetration of a number a by a positive integer b, denoted by a↑↑b or ^ba, is recursively defined by:

a↑↑1 = a,
a↑↑(k+1) = a^(a↑↑k).

Thus we have e.g. 3↑↑2 = 3³ = 27, hence 3↑↑3 = 3²⁷ = 7625597484987 and 3↑↑4 is roughly 10^{3.6383346400240996*10^12}.

Find the last 8 digits of 1777↑↑1855.

题目：

hyperexponentiation 或者 tetration 即中文意译的超幂，数字 a 的超幂 b 次，可以写成 a↑↑b 或 ^ba 的形式，超幂以如下递归的形式定义：


a↑↑1 = a,
a↑↑(k+1) = a^(a↑↑k).


因此，我们可以计算出，比如 3↑↑2 = 3³ = 27， 然后是，3↑↑3 = 3²⁷ = 7625597484987 ，接着的 3↑↑4 大概等于10^{3.6383346400240996*10^12}

请给出 1777↑↑1855 的最后 8 位。

jerryxjr1220

这题炒鸡简单

1. import sys
   
2. sys.setrecursionlimit(10000)
   
3. def uparrow(a,b,m):
   
4.     if b==1: return a%m
   
5.     return pow(a,uparrow(a,b-1,m),m)
   
6. print (uparrow(1777,1855,10**8))

复制代码

95962097
[Finished in 0.1s]

永恒的蓝色梦想

这题确实不难，快速幂搞定

C++ 1ms

1. #include<iostream>
   
2. 
   
3. 
   
4. 
   
5. int main() {
   
6.     using namespace std;
   
7.     ios::sync_with_stdio(false);
   
8. 
   
9.     constexpr unsigned int MOD = 100000000;
   
10.     unsigned long long res = 1777, base, temp;
    
11. 
    
12. 
    
13.     for (unsigned short n = 1854; n; n--) {
    
14.         temp = res;
    
15.         res = 1;
    
16.         base = 1777;
    
17. 
    
18.         while (temp) {
    
19.             if (temp & 1) {
    
20.                 res = res * base % MOD;
    
21.             }
    
22. 
    
23.             base = base * base % MOD;
    
24.             temp >>= 1;
    
25.         }
    
26.     }
    
27. 
    
28. 
    
29.     cout << res << endl;
    
30.     return 0;
    
31. }

复制代码

guosl

补充上面算法的理论证明：
由于gcd(1777,10^8)=1，所以根据数论中的Eulor定理知一定存在一个M使得1777^M=1 MOD 10^8。根据计算最小的M=1250000，又10^8=40*1250000，从而
1777^(10^8*p+q)=1777^q MOD 10^8，即1777^x=1777^(x MOD 10^8) MOD 10^8

永恒的蓝色梦想

Python

1. res = 1777
   
2. 
   
3. for _ in range(1854):
   
4.     res = pow(1777, res, 100000000)
   
5. 
   
6. print(res)

复制代码