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

Как узнать цифру единиц определенного номера (например, 3 power 2011). Какую логику я должен использовать, чтобы найти ответ на эту проблему?

Ответ 1

Для основания 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 <

сначала возьмите базовый mod 10 = > : = i
перейдите в индекс 4*i в нашей таблице (это начальное смещение этой конкретной цифры)
возьмем экспоненту mod 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 (то есть их gcd равно 1). Цифры < 10 co-prime to 10 - 1,3,7 и 9. Таким образом, phi (10) = 4, и это доказывает, что действительно a^4 mod 10 = 1 mod 10.

Последнее утверждение, что доказывается, состоит в том, что для экспоненциальности, где база равнa >= 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.

Ответ 2

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

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

Вот базовый пример в JavaScript: http://jsfiddle.net/dtyuA/2/

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

Ответ 3

Вы должны посмотреть Модульное возведение в степень. То, что вы хотите, это то же самое, что и вычисление 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 для желаемой базы и экспоненты, и там ваш ответ.

EDIT: для еще более простого метода, менее эффективного по сравнению с процессором, но с большей памятью, ознакомьтесь с разделом Memory-efficient статья в Википедии. Логика достаточно проста:

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

Ответ 4

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

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

Ответ 5

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

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

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

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

Нам также нужно вычислить, что totient, или значение phi, равно 10. Для 10 это 4. Для 100 phi - 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.

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

Ответ 6

Вы ppl усложняют задачу.

Предположим, что u хочет узнать цифру элемента 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.

Ответ 7

Bellow - это таблица с мощностью и цифрой устройства 3 от этой мощности.

0 1
1 3
2 9
3 7
4 1
5 3
6 9
7 7

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

Ответ 8

Вот трюк, который работает для чисел, которые не кратно коэффициенту базы (для базы 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 не работают).

Ответ 9

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

Ответ 10

Если у вас есть номер и экспонента, отделите его.

Пусть 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

Пояснение:

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

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

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

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

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