如何确定 C++14 中 4^(4^(10^9))%9^9 的值？

Question

我已经用 9^(10^9) 这样的数字成功地尝试了大 mod 算法。但是当功率也大到无法使用时，如何得出最终的答案呢？

#include <iostream>
#include <cmath>
#define ULL unsigned long long
using namespace std;

ULL mod(ULL b, ULL p,ULL m)
{
    ULL md=1,c;
    while(p!=0)
{
    if (p % 2 == 0)
    {
        md*=(b%m)*(b%m);
        p=p/2;
    }
    else 
    {
        md*=(b % m);
        p--;
    }
}
    return md;
}

int main()
{
ULL b=4, p, m=pow(9,9), num,res;
cin >> p;
num= mod(b,p,m);
res=pow(num,4);
cout << res;
}

Answer 1

考虑计算 (4^(p))%(9^9) 的一般情况，其中 p 是一个大数（在本例中 p = 4^(10^9)）。考虑 4 模 9^9 的幂序列：(4^0)%(9^9) == 1, (4^1)%(9^9) == 4, (4^2)%(9 ^9) == 16，最终在 t（t 未知）个循环之后，序列将循环回到 (4^t)%(9^9) == 1，然后重复。（注意数字必须是 "coprime"，否则经过一些循环后，结果变为零并保持为零。）因此计算可以使用 p%t 而不是 p:

(4^(p))%(9^9) == (4^(p%t))%(9^9)

这看起来很大，但 t 将 <= 9^9，9^9 < 2^29，4 * 2^29 = 2^31，所以 64 位整数（需要平方来加速向上指数）将足以解决这个问题。所以现在的问题是解决t。您可以从 | 开始确定 t米 = 1 | t = 0 |然后循环 | m = (m*4)%(9^9) | t += 1 |直到 m == 1 再次。

例如，假设您正在寻找这样的 t：

(4^(p))%9 == (4^(p%t))%9

对于这个更简单的示例：

(4^0)%9 == 1      ;m == 1, t == 0
(4^1)%9 == 4      ;m == 4, t == 1
(4^2)%9 == 7      ;m == 7, t == 2
(4^3)%9 == 1      ;m == 1, t == 3   (end of loop)

所以 t == 3（对于这个更简单的例子）：

(4^(p))%9 == (4^(p%3))%9

正如DAle所评论的，还有与totient相关的欧拉定理：

https://en.wikipedia.org/wiki/Euler%27s_totient_function#Euler.27s_theorem

如果a和n互质，则

(a^(ϕ(n)))%n = 1, where ϕ(n) is the totient function.

Wiki 文章还包含一个 totient 函数的公式。

https://en.wikipedia.org/wiki/Euler%27s_totient_function#Euler.27s_product_formula

你可以使用 t = ϕ(9^9)。这不是满足 (4^(t))%(9^9) = 1 的 t 的最小值，但它已经足够好了。

问题发布已经两天了，所以继续

t = ϕ(9^9) = ϕ(3^18) = (3^18)(1-1/3) = 2(3^17) = 258280326

利用循环法求出一个较小的值，t = 3^17 = 129140163，然后用于内幂模

p%t = ( (4^(10^9)) % 129140163 ) = 19457986

然后继续外幂模的过程

(4^(4^(10^9)))%(9%9) = (4^19457986)%(9^9) = 335228719

示例代码：

#include <stdio.h>

typedef unsigned long long uint64_t;

/* count number of cycles t such that */
/* (v^t)%m = 1 */
uint64_t cntcyc(uint64_t v, uint64_t m)
{
uint64_t t = 0;
uint64_t i = 1;
    do {
        i = (i * v) % m;
        t++;
    } while (i != 1);
    return t;
}

/* v to power p modulo m */
uint64_t powmod(uint64_t v, uint64_t p, uint64_t m)
{
uint64_t s = v;                         /* repeated square */
uint64_t r = 1;                             /* result */
    while(p){
        if(p&1)
            r = (r*s)%m;
        s = (s*s)%m;
        p >>= 1;
    }
    return r;
}

int main()
{
uint64_t r;
    r = cntcyc(4ull, 387420489ull);      /* 4, 9^9 */
    printf("%llu\n", r);                 /*   129140163 */
    r = powmod(4ull, 1000000000ull, r);  /* (4^(10^9))%r */
    printf("%llu\n", r);                 /*   19457986 */
    r = powmod(4ull, r, 387420489ull);   /* (4^r)%(9^9) */
    printf("%llu\n", r);                 /*   335228719 */
    r = 258280326ull;                    /* r = totient(9^9) */
    r = powmod(4ull, 1000000000ull, r);  /* (4^(10^9))%r */
    printf("%llu\n", r);                 /*   19457986 */
    r = powmod(4ull, r, 387420489ull);   /* (4^r)%(9^9) */
    printf("%llu\n", r);                 /*   335228719 */
    r = 258280326ull;                    /* r = totient(9^9) */
    r = powmod(4ull, 1000000000ull, r);  /* (4^(10^9))%r */
    /* show that r += 3^17 doesn't effect final result */
    r += 129140163ull;                   /* r += 3^17 */
    printf("%llu\n", r);                 /*   148598149 */
    r = powmod(4ull, r, 387420489ull);   /* (4^r)%(9^9) */
    printf("%llu\n", r);                 /*   335228719 */
    return 0;
}

如何确定 C++14 中 4^(4^(10^9))%9^9 的值？

How can I determine the value of 4^(4^(10^9))%9^9 in C++14?

c++

algorithm

c++14

mod

bigmod