Надеюсь такой формат по душе. Хочется побольше инфы скинуть, но спамить по 17 постов не хочется :)
Вчера с другом решали прикольный 3kye:
Последние цифры степеней цикличны:
Для любого числа последние цифры его степеней повторяются с определенным периодом (обычно 4 для модуля 10)
Например, для 3: 3^1 = 3, 3^2 = 9, 3^3 = 7, 3^4=1, 3^5=3 (цикл 4)
------------------------------------------------------------------------------------------------------
Период зависит от ф(10) = 4 (теорема Эйлера). Период числа a зависит от a mod 10, но максимальный период равен 4.
------------------------------------------------------------------------------------------------------
a^b mod 10 если a = 0 mod 10, то a ^ b = 0 mod 10 для b >= 1
Иначе a^b mod 10 как a ^ ((b mod lambda(10)) + lambda(10)) mod 10, где lambda - функция Кармайкла (lambda(10) = 4)
------------------------------------------------------------------------------------------------------
Тогда код на плюсах будет выглядеть так:
#include <list>
#include <iostream>
#include <cmath>
using namespace std;
int last_digit(list<int> array) {
int someledigit = 1;
for (list<int>::iterator i = array.end(); i != array.begin();) someledigit = pow(--i == array.begin() ? *i % 10 : *i < 4 ? *i : *i % 4 + 4, someledigit < 4 ? someledigit : someledigit % 4 + 4);
return someledigit % 10;
}
Последние цифры степеней цикличны:
Для любого числа последние цифры его степеней повторяются с определенным периодом (обычно 4 для модуля 10)
Например, для 3: 3^1 = 3, 3^2 = 9, 3^3 = 7, 3^4=1, 3^5=3 (цикл 4)
------------------------------------------------------------------------------------------------------
Период зависит от ф(10) = 4 (теорема Эйлера). Период числа a зависит от a mod 10, но максимальный период равен 4.
------------------------------------------------------------------------------------------------------
a^b mod 10 если a = 0 mod 10, то a ^ b = 0 mod 10 для b >= 1
Иначе a^b mod 10 как a ^ ((b mod lambda(10)) + lambda(10)) mod 10, где lambda - функция Кармайкла (lambda(10) = 4)
------------------------------------------------------------------------------------------------------
Тогда код на плюсах будет выглядеть так:
#include <list>
#include <iostream>
#include <cmath>
using namespace std;
int last_digit(list<int> array) {
int someledigit = 1;
for (list<int>::iterator i = array.end(); i != array.begin();) someledigit = pow(--i == array.begin() ? *i % 10 : *i < 4 ? *i : *i % 4 + 4, someledigit < 4 ? someledigit : someledigit % 4 + 4);
return someledigit % 10;
}