Посчитать значение выражения с большими числами, как?

Question

[rastr]

Задано целое число N. Вычислите следующие выражение: (1^N + 2^N + 3^N + 4^N) mod 5,
где 0 <= N <= 10^100000
Работа программы не должна превышать 0.2 секунды.

Comments

[Lynn «Кофеман»]

Подсказка:

> for (let i = 0; i < 10; i++) { console.log(3**i % 5) }
1
3
4
2
1
3
4
2
1
3

Answer 1

[Rsa97]

(1^N + 2^N + 3^N + 4^N) mod 5 = (1 + 2^{N mod 4} + 3^{N mod 4} + 4^{N mod 4}) mod 5

Comments

[Дмитрий]

4 в степени N mod 2 даже

[Rsa97]

Дмитрий, Можно. Это я для однообразия оставил.

[Wataru]

Rsa97, Возможно, стоит дополнить, что вы тут применили малую теорему ферма, чтобы было понятно, откуда это взялось.

Еще, для нахождения N%4, достаточно взять 2 последних цифры в длинном числе N, если кому-то не очевидно.