Как я могу определить значение 4 ^ (4 ^ (10 ^ 9))% 9 ^ 9 в C ++ 14?

Рассмотрим общий случай вычисления (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, после чего она повторяется. Таким образом, расчет может использовать p% t вместо p:

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

Это кажется большим, но т будет <= 9 ^ 9 и 9 ^ 9 < 2 ^ 29 и 4 * 2 ^ 29 = 2 ^ 31, поэтому 32-разрядные целые числа будут достаточно большими, чтобы решить эту проблему. Так что проблема сейчас заключается в том, чтобы решить за т. Вы можете определить т, начав с | m = 1 | t = 0 | а затем цикл с | m = (m * 4)% (9 ^ 9) | t + = 1 | пока m == 1 снова.

Например, скажем, вы искали т, что:

(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.

Статья в вики также содержит формулу для функции totient.

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

Вы можете использовать t = ϕ (9 ^ 9). Это не будет наименьшее значение для t, которое будет удовлетворять (4 ^ (t))% (9 ^ 9) = 1, но оно будет достаточно хорошим.

Прошло два дня с тех пор, как вопрос был опубликован, поэтому продолжаем

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

Использование метода цикла находит меньшее значение, t = 3 ^ 17 = 129140163. Затем оно используется для внутренней мощности по модулю

(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;
}