Как проверить делимость числа не в базе 10 без конвертации?

Question

Допустим, у меня есть номер базы 3, 1211. Как я могу проверить, что это число делится на 2 без преобразования его обратно в базу 10?

Обновление
Оригинальная проблема от TopCoder
Цифры 3 и 9 имеют интересное свойство. Если вы берете любое кратное 3 и суммируете его цифры, вы получаете другое кратное 3. Например, 118 * 3 = 354 и 3 + 5 + 4 = 12, что является кратным 3. Аналогично, если вы берете любое кратное число 9 и суммируя его цифры, вы получите еще одно кратное 9. Например, 75 * 9 = 675 и 6 + 7 + 5 = 18, что кратно 9. Вызовите любую цифру, для которой это свойство представляет интерес, кроме 0 и 1, для которых свойство выполняется тривиально. Цифра, которая интересна в одной базе, не обязательно интересна в другой базе. Например, 3 интересна для базы 10, но неинтересна для базы 5. При наличии базы int ваша задача состоит в том, чтобы возвращать все интересные цифры для этой базы в порядке возрастания. Чтобы определить, интересна ли конкретная цифра или нет, вам не нужно учитывать все кратные цифры. Вы можете быть уверены, что если свойство выполняется для всех кратных цифр с числом менее четырех цифр, то оно также сохраняется для кратных чисел с большим количеством цифр. Например, в базе 10 вам не нужно учитывать множители, превышающие 999.
Примечания
- Если база больше 10, цифры могут иметь числовое значение больше 9. Поскольку целые числа по умолчанию отображаются в базе 10, не пугайтесь, если такие цифры появляются на экране как несколько десятичных цифр. Например, одна из интересных цифр в базе 16 - 15.
Препятствия
- база от 3 до 30 включительно.

Это мое решение:

class InterestingDigits {
public:
    vector<int> digits( int base ) {
        vector<int> temp;
        for( int i = 2; i <= base; ++i )
            if( base % i == 1 )
                temp.push_back( i );
        return temp;
    }
};

Трюк был хорошо объяснен здесь: https://math.stackexchange.com/questions/17242/how-does-base-of-a-number-relate-to-modulos-of-its-each-individual-digit

Спасибо
Чан

Answer 1

Если ваше число k находится в третьей базе, вы можете записать его как

k = a0 3^n + a1 3^{n-1} + a2 3^{n-2} + ... + an 3^0

, где a0, a1, ..., an - цифры в представлении базовой тройки.

Чтобы узнать, делится ли число на два, вас интересует, равно ли число по модулю 2 нулю.Хорошо, k mod 2 задается как

k mod 2 = (a0 3^n + a1 3^{n-1} + a2 3^{n-2} + ... + an 3^0) mod 2
        = (a0 3^n) mod 2 + (a1 3^{n-1}) mod 2 + ... + an (3^0) mod 2
        = (a0 mod 2) (3^n mod 2) + ... + (an mod 2) (3^0 mod 2)

Хитрость здесь в том, что 3 ^ i = 1 (mod 2), поэтому это выражение равно

k mod 2 = (a0 mod 2) + (a1 mod 2) + ... + (an mod 2)

Другими словами, еслиВы суммируете цифры троичного представления и получаете, что это значение делится на два, тогда само число должно делиться на два.Чтобы сделать это еще круче, поскольку единственными троичными цифрами являются 0, 1 и 2, это равносильно тому, чтобы спросить, является ли число 1 в троичном представлении четным!

В более общем случае, есличисло в базе m, то это число делится на m - 1, если сумма цифр делится на m.Вот почему вы можете проверить, делится ли число в базе 10 на 9, суммируя цифры и посмотрев, делится ли это значение на девять.

Answer 2

Вы всегда можете построить конечный автомат для любой базы и любого делителя:

Обычно для вычисления значения n строки цифр в базе b вы перебираете цифры и делаете

n = (n * b) + d

для каждой цифры d.

Теперь, если вы заинтересованы в делимости, вы делаете это по модулю m вместо:

n = ((n * b) + d) % m

Здесь n может принимать не более m различных значений. Возьмите их как состояния конечного автомата и вычислите переходы в зависимости от цифры d согласно этой формуле. Принимающим является состояние, в котором остаток равен 0.

Для вашего конкретного случая у нас есть

n == 0, d == 0: n = ((0 * 3) + 0) % 2 = 0
n == 0, d == 1: n = ((0 * 3) + 1) % 2 = 1
n == 0, d == 2: n = ((0 * 3) + 2) % 2 = 0
n == 1, d == 0: n = ((1 * 3) + 0) % 2 = 1
n == 1, d == 1: n = ((1 * 3) + 1) % 2 = 0
n == 1, d == 2: n = ((1 * 3) + 2) % 2 = 1

, который показывает, что вы можете просто сложить цифры 1 по модулю 2 и игнорировать любые цифры 0 или 2.

Answer 3

То же, что и в базе 10, для вашего примера: 1. Найдите кратное 2, равное <= 1211, то есть 1210 (см. Ниже, как этого добиться) 2. Субъект 1210 от 1211, вы получите 1 3. 1 <10, поэтому 1211 не делится на 2 </p>

как добиться 1210: 1. начинается с 2 2. 2 + 2 = 11 3. 11 + 2 = 20 4. 20 + 2 = 22 5. 22 + 2 = 101 6. 101 + 2 = 110 7. 110 + 2 = 112 8. 112 + 2 = 121 9. 121 + 2 = 200 10. 200 + 2 = 202 ... // повторяем, пока не получим наибольшее число <= 1211 это в основном то же самое, что и база 10, это просто округление до 3 вместо 10. </p>

Answer 4

Добавьте все цифры вместе (или даже просто посчитайте их) - если ответ нечетный, число нечетное; если оно четное, то число четное.

Как это работает? Каждая цифра из числа вносится 0, 1 или 2 раза (1, 3, 9, 27, ...). 0 или 2 добавляет четное число, поэтому не влияет на четность / четность (четность) числа в целом. 1 добавляет одну из степеней 3, которая всегда нечетна, и таким образом меняет четность). И мы начинаем с 0 (даже). Таким образом, подсчитав, является ли количество сальто нечетным или четным, мы можем определить, является ли само число.

Answer 5

Я не уверен, на каком процессоре у вас есть число в base-3, но нормальный способ сделать это - выполнить операцию модуля / остатка.

if (n % 2 == 0) {
    // divisible by 2, so even
} else {
    // odd
}

Как реализовать модульОператор будет зависеть от того, как вы храните свой номер базы-3.Простейший код, вероятно, будет состоять в том, чтобы реализовать обычное длинное деление карандашом и бумагой и получить от этого остаток.

    0 2 2 0
    _______
2 ⟌ 1 2 1 1 
    0
    ---
    1 2
    1 1
    -----
      1 1
      1 1
      -----
        0 1 <--- remainder = 1 (so odd)

(Это работает независимо от базы, для «базы-3» существуют «хитрости»как уже упоминали другие)