欧拉计划 发表于 2016-10-5 15:59:51

题目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 = 33 = 27, hence 3↑↑3 = 327 = 7625597484987 and 3↑↑4 is roughly 103.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 = 33 = 27， 然后是，3↑↑3 = 327 = 7625597484987 ，接着的 3↑↑4 大概等于103.6383346400240996*10^12

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

jerryxjr1220 发表于 2017-9-22 11:39:47

这题炒鸡简单{:10_319:}
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

永恒的蓝色梦想 发表于 2020-4-27 15:08:38

本帖最后由 永恒的蓝色梦想 于 2021-2-11 15:21 编辑

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

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 发表于 2020-5-17 21:42:30

补充上面算法的理论证明：
由于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

永恒的蓝色梦想 发表于 2020-6-23 10:44:51

本帖最后由 永恒的蓝色梦想 于 2021-2-11 15:18 编辑

Pythonres = 1777

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

print(res)
页: [1]
查看完整版本: 题目188：数字的超幂