题目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

这题炒鸡简单

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

95962097
[Finished in 0.1s]

永恒的蓝色梦想

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

C++ 1ms

#include<iostream>



int main() {
    using namespace std;
    ios::sync_with_stdio(false);

    constexpr unsigned int MOD = 100000000;
    unsigned long long res = 1777, base, temp;


    for (unsigned short n = 1854; n; n--) {
        temp = res;
        res = 1;
        base = 1777;

        while (temp) {
            if (temp & 1) {
                res = res * base % MOD;
            }

            base = base * base % MOD;
            temp >>= 1;
        }
    }


    cout << res << endl;
    return 0;
}

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

res = 1777

for _ in range(1854):
    res = pow(1777, res, 100000000)

print(res)