Как найти разряд единиц определенной степени самым простым способом

Для базы 3:

3^1 = 3
3^2 = 9
3^3 = 27
3^4 = 81
3^5 = 243
3^6 = 729
3^7 = 2187
...

То есть цифра единиц имеет только 4 возможности, а затем повторяется в одном и том же цикле.

С помощью теоремы Эйлера мы можем показать, что это верно для любого целого числа n, т.е. цифра единиц будет повторяться не более чем через 4 последовательных показателя степени. Взгляд только на цифру единиц произвольного произведения эквивалентен получению остатка от умножения по модулю 10, например:

2^7 % 10 = 128 % 10 = 8 

Также можно показать (и довольно интуитивно), что для произвольной базы цифра единиц любой степени будет зависеть только от цифры единиц самой базы, то есть 2013 ^ 2013 имеет ту же цифру единиц, что и 3 ^ 2013.

Мы можем использовать оба факта для создания чрезвычайно быстрого алгоритма (спасибо за help - с любезного разрешения я могу представить гораздо более быструю версию).

Идея такова: поскольку мы знаем, что для любого числа от 0 до 9 будет не более 4 различных результатов, мы также можем сохранить их в таблице поиска:

{ 0,0,0,0, 1,1,1,1, 6,2,4,8, 1,3,9,7, 6,4,6,4, 
  5,5,5,5, 6,6,6,6, 1,7,9,3, 6,8,4,2, 1,9,1,9 }

Это возможные исходы от 0 до 9 в указанном порядке, сгруппированные по четыре. Теперь идея заключается в возведении в степень n ^ a до

• сначала возьми базовый мод 10 => := i
• перейти к индексу 4*i в нашей таблице (это начальное смещение этой конкретной цифры)
• возьмем показатель степени по модулю 4 => := off (как утверждает теорема Эйлера, у нас есть только четыре возможных результата!)
• добавьте off к 4*i, чтобы получить результат

Теперь, чтобы сделать это максимально эффективным, к основным арифметическим операциям применяются некоторые настройки:

• Умножение на 4 эквивалентно сдвигу на два влево ('‹‹ 2')
• Получение числа a % 4 эквивалентно произнесению a&3 (маскируя биты 1 и 2, которые образуют остаток % 4)

Алгоритм на C:

static int table[] = {
    0, 0, 0, 0, 1, 1, 1, 1, 6, 2, 4, 8, 1, 3, 9, 7, 6, 4, 6, 4, 
    5, 5, 5, 5, 6, 6, 6, 6, 1, 7, 9, 3, 6, 8, 4, 2, 1, 9, 1, 9
};

int /* assume n>=0, a>0 */ 
unit_digit(int n, int a)
{
    return table[((n%10)<<2)+(a&3)];
}

Подтверждение первоначальных утверждений

Из наблюдений мы заметили, что цифра единиц для 3^x повторяется в каждой четвертой степени. Утверждалось, что это верно для любого целого числа. Но как это на самом деле доказано? Как оказалось, использовать модульную арифметику довольно просто. Если нас интересует только цифра единиц, мы можем выполнить наши вычисления по модулю 10. Это эквивалентно тому, что цифра единиц повторяется после 4 показателей степени или сказать

a^4 congruent 1 mod 10

Если это так, то например

a^5 mod 10 = a^4 * a^1 mod 10 = a^4 mod 10 * a^1 mod 10 = a^1 mod 10

то есть a ^ 5 дает ту же цифру единиц, что и a ^ 1, и так далее.

Из теоремы Эйлера мы знаем, что

a^phi(10) mod 10 = 1 mod 10

где phi(10) — это числа от 1 до 10, которые взаимно просты с 10 (т. е. их НОД равен 1). Числа ‹ 10 взаимно просты с 10 — это 1,3,7 и 9. Итак, фи(10) = 4, и это доказывает, что действительно a^4 mod 10 = 1 mod 10.

Последнее утверждение, которое нужно доказать, заключается в том, что для возведения в степень, где основание >= 10, достаточно просто посмотреть на цифру единиц основания. Допустим, наша база равна x >= 10, поэтому мы можем сказать, что x = x_0 + 10*x_1 + 100*x_2 + ... (представление по базе 10)

Используя модульное представление, легко увидеть, что действительно

x ^ y mod 10
= (x_0 + 10*x_1 + 100*x_2 + ...) ^ y mod 10
= x_0^y + a_1 * (10*x_1)^y-1 + a_2 * (100*x_2)^y-2 + ... + a_n * (10^n) mod 10
= x_0^y mod 10  

где a_i — коэффициенты, включающие степени x_0, но, в конечном счете, не относящиеся к делу, поскольку весь продукт a_i * (10 * x_i)^y-i будет делиться на 10.

Вы должны посмотреть на Модульное возведение в степень. То, что вам нужно, это то же самое, что и вычисление n^e (mod m) с m = 10. Это то же самое, что и вычисление остатка от деления на десять от n^e.

Вы, вероятно, заинтересованы в бинарном методе справа налево для вычисления его, так как он наиболее экономичен по времени и самый простой, не слишком сложный в реализации. Вот псевдокод из Википедии:

function modular_pow(base, exponent, modulus)
    result := 1
    while exponent > 0
        if (exponent & 1) equals 1:
           result = (result * base) mod modulus
        exponent := exponent >> 1
        base = (base * base) mod modulus
    return result

После этого просто вызовите его с модулем = 10 для желаемой базы и показателя степени, и вот ваш ответ.

РЕДАКТИРОВАТЬ: для еще более простого метода, менее эффективного с точки зрения ЦП, но более разумного с точки зрения памяти, проверьте Эффективное использование памяти статьи в Википедии. Логика достаточно проста:

function modular_pow(base, exponent, modulus)
    c := 1
    for e_prime = 1 to exponent 
        c := (c * base) mod modulus
    return c

Я уверен, что есть правильный математический способ решить эту проблему, но я бы предположил, что, поскольку вы заботитесь только о последней цифре и поскольку теоретически каждое число, многократно умноженное само на себя, должно в конечном итоге генерировать повторяющийся шаблон (если смотреть только на последнюю цифру ), вы можете просто выполнять умножения до тех пор, пока не обнаружите первое повторение, а затем сопоставьте свой показатель степени с соответствующей позицией в построенном шаблоне.

Обратите внимание, что, поскольку вас интересует только последняя цифра, вы можете еще больше упростить задачу, усекая введенное число до единицы, прежде чем начнете строить отображение шаблона. Это позволит вам определить последнюю цифру даже для произвольно больших входных данных, которые в противном случае вызвали бы переполнение при первом или втором умножении.

Вот простой пример на JavaScript: http://jsfiddle.net/dtyuA/2/

function lastDigit(base, exponent) {
  if (exponent < 0) {
    alert("stupid user, negative values are not supported");
    return 0;
  }
  if (exponent == 0) {
    return 1;
  }
  var baseString = base + '';
  var lastBaseDigit = baseString.substring(baseString.length - 1);
  var lastDigit = lastBaseDigit;
  var pattern = [];

  do {
    pattern.push(lastDigit);
    var nextProduct = (lastDigit * lastBaseDigit) + '';
    lastDigit = nextProduct.substring(nextProduct.length - 1);
  } while (lastDigit != lastBaseDigit);

  return pattern[(exponent - 1) % pattern.length];
};

function doMath() {
  var base = parseInt(document.getElementById("base").value, 10);
  var exp = parseInt(document.getElementById("exp").value, 10);
  console.log(lastDigit(base, exp));
};

console.log(lastDigit(3003, 5));

Base: <input id="base" type="text" value="3" /> <br> 
Exponent: <input id="exp" type="text" value="2011"><br>
<input type="button" value="Submit" onclick="doMath();" />

Кстати, последняя цифра в 3^2011 — 7.

Мы можем начать с проверки последней цифры каждого результата, полученного путем возведения десятичных цифр в последовательные степени:

d      d^2    d^3    d^4    d^5    d^6    d^7    d^8    d^9 (mod 10)
---    ---    ---    ---    ---    ---    ---    ---    ---
0      0      0      0      0      0      0      0      0
1      1      1      1      1      1      1      1      1
2      4      8      6      2      4      8      6      2
3      9      7      1      3      9      7      1      3
4      6      4      6      4      6      4      6      4
5      5      5      5      5      5      5      5      5
6      6      6      6      6      6      6      6      6
7      9      3      1      7      9      3      1      7
8      4      2      6      8      4      2      6      8
9      1      9      1      9      1      9      1      9

Мы видим, что во всех случаях последняя цифра проходит не более четырех различных значений. Используя этот факт и предполагая, что n — неотрицательное целое число, а p — положительное целое число, мы можем вычислить результат достаточно напрямую (например, в Javascript):

function lastDigit(n, p) {
    var d = n % 10;
    return [d, (d*d)%10, (d*d*d)%10, (d*d*d*d)%10][(p-1) % 4];
}

... или еще проще:

function lastDigit(n, p) {
    return Math.pow(n % 10, (p-1) % 4 + 1) % 10;
}

lastDigit(3, 2011)
/* 7 */

Вторая функция эквивалентна первой. Обратите внимание, что хотя он использует возведение в степень, он никогда не работает с числом больше девяти в четвертой степени (6561).

Ключ к решению этого типа вопросов лежит в теореме Эйлера.

Эта теорема позволяет нам сказать, что a^phi(m) mod m = 1 mod m тогда и только тогда, когда а и т взаимно просты. То есть a и m не делятся без остатка. Если это так (а для вашего примера это так), мы можем решить проблему на бумаге, без какого-либо программирования.

Давайте найдем цифру единицы 3 ^ 2011, как в вашем примере. Это эквивалентно 3^2011 mod 10.

Первый шаг — проверить, являются ли числа 3 и 10 взаимно простыми. Они не делятся без остатка, поэтому мы можем использовать теорему Эйлера.

Нам также необходимо вычислить значение totient, или значение фи, для 10. Для 10 , это 4. Для 100 фи это 40, 1000 это 4000 и т.д.

Используя теорему Эйлера, мы видим, что 3^4 mod 10 = 1. Затем мы можем переписать исходный пример так:

3^2011 mod 10 = 3^(4*502 + 3) mod 10 = 3^(4*502) mod 10 + 3^3 mod 10 = 1^502 * 3^3 mod 10 = 27 mod 10 = 7

Таким образом, последняя цифра 3^2011 равна 7.

Как вы видели, это не требовало никакого программирования, и я решил этот пример на листе бумаги.

Вы, чел, усложняете простые вещи.

Предположим, вы хотите узнать единичную цифру abc ^ xyz.

divide the power xyz by 4,if remainder is 1 ans is c^1=c.
 if xyz%4=2 ans is unit digit of  c^2.
 else if xyz%4=3 ans is unit digit of  c^3.

 if xyz%4=0 
 then we need to check whether c is 5,then ans is 5
  if c is even ans is 6
 if c is odd (other than 5 ) ans is 1.

Ниже приведена таблица со степенью и единицей измерения 3 в этой степени.
0 1
1 3
2 9
3 7
4 1
5 3
6 9
7 7

Используя эту таблицу, вы можете видеть, что цифра единицы может быть 1, 3, 9, 7, и последовательность повторяется в этом порядке для более высоких степеней 3. Используя эту логику, вы можете найти, что цифра единицы (3 степень 2011) равна 7 Вы можете использовать тот же алгоритм для общего случая.

Вот трюк, который работает для чисел, которые не кратны множителю основания (для основания 10 оно не может быть кратным 2 или 5). Давайте используем основание 3. То, что вы пытаетесь найти, это 3^2011 mod 10. Найдите степень числа 3, начиная с 3^1, пока не найдете число с последней цифрой 1. Для 3 вы получите 3^4=81. Запишите исходную мощность как (3^4)^502*3^3. Используя модульную арифметику, (3 ^ 4) ^ 502 * 3 ^ 3 сравнимо (имеет ту же последнюю цифру, что и) 1 ^ 502 * 3 ^ 3. Таким образом, 3^2011 и 3^3 имеют одинаковую последнюю цифру — 7.

Вот некоторый псевдокод, чтобы объяснить это в целом. Это находит последнюю цифру b^n в базе B.

// Find the smallest power of b ending in 1.
i=1
while ((b^i % B) != 1) {
    i++
}
// b^i has the last digit 1

a=n % i
// For some value of j, b^n == (b^i)^j * b^a, which is congruent to b^a
return b^a % B

Вам нужно быть осторожным, чтобы предотвратить бесконечный цикл, если никакая степень b не заканчивается на 1 (в базе 10 числа, кратные 2 или 5, не работают).

Найдите повторяющийся набор в этом случае, это 3,9,7,1, и он повторяется в том же порядке навсегда .... поэтому разделите 2011 на 4, что даст вам напоминание 3. Это 3-й элемент в повторяющемся наборе. Это самый простой способ найти для любого заданного нет. скажем, если попросить 3 ^ 31, то напоминание о 31/4 равно 3, и поэтому 7 - это цифра единицы. для 3 ^ 9 9/4 равно 1, поэтому единицей будет 3. 3 ^ 100, единицей будет 1.

Если у вас есть число и показатель степени, это легко.

Пусть n1 — число, а n2 — мощность. А ** представляет силу.

предположим, что n1>0.

% означает деление по модулю.

псевдокод будет выглядеть так

def last_digit(n1, n2)
  if n2==0 then return 1 end
  last = n1%10
  mod = (n2%4).zero? ? 4 : (n2%4)
  last_digit = (last**mod)%10
end

Объяснение:

Нам нужно учитывать только последнюю цифру числа, потому что она определяет последнюю цифру мощности. это свойство математики состоит в том, что подсчет вероятности каждой цифры (0-9) мощности последней цифры не превышает 4.

1) Теперь, если показатель степени равен нулю, мы знаем, что последняя цифра будет 1.

2) Получить последнюю цифру на %10 от числа (n1)

3)% 4 в показателе степени (n2) - если выход равен нулю, мы должны рассматривать это как 4, потому что n2 не может быть нулевым. если %4 не равно нулю, мы должны учитывать значение %4.

4) теперь у нас не более 9**4. Компьютеру это легко вычислить. возьмите% 10 на этом номере. У вас есть последняя цифра.